C++ program to find Inorder successor in a BST

BST_InorderSuccessor_CPP.cpp

/* C++ program to find Inorder successor in a BST */
#include<iostream>
using namespace std;
struct Node {
	int data;
	struct Node *left;
	struct Node *right;
};

//Function to find some data in the tree
Node* Find(Node*root, int data) {
	if(root == NULL) return NULL;
	else if(root->data == data) return root;
	else if(root->data < data) return Find(root->right,data);
	else return Find(root->left,data);
}

//Function to find Node with minimum value in a BST
struct Node* FindMin(struct Node* root) {
	if(root == NULL) return NULL;
	while(root->left != NULL)
		root = root->left;
	return root;
}

//Function to find Inorder Successor in a BST
struct Node* Getsuccessor(struct Node* root,int data) {
	// Search the Node - O(h)
	struct Node* current = Find(root,data);
	if(current == NULL) return NULL;
	if(current->right != NULL) {  //Case 1: Node has right subtree
		return FindMin(current->right); // O(h)
	}
	else {   //Case 2: No right subtree  - O(h)
		struct Node* successor = NULL;
		struct Node* ancestor = root;
		while(ancestor != current) {
			if(current->data < ancestor->data) {
				successor = ancestor; // so far this is the deepest node for which current node is in left
				ancestor = ancestor->left;
			}
			else
				ancestor = ancestor->right;
		}
		return successor;
	}
}
 
//Function to visit nodes in Inorder
void Inorder(Node *root) {
	if(root == NULL) return;
 
	Inorder(root->left);       //Visit left subtree
	printf("%d ",root->data);  //Print data
	Inorder(root->right);      // Visit right subtree
}
 
// Function to Insert Node in a Binary Search Tree
Node* Insert(Node *root,char data) {
	if(root == NULL) {
		root = new Node();
		root->data = data;
		root->left = root->right = NULL;
	}
	else if(data <= root->data)
		root->left = Insert(root->left,data);
	else 
		root->right = Insert(root->right,data);
	return root;
}
 
int main() {
	/*Code To Test the logic
	  Creating an example tree
	                    5
			   / \
			  3   10
			 / \   \
			1   4   11
    */
	Node* root = NULL;
	root = Insert(root,5); root = Insert(root,10);
	root = Insert(root,3); root = Insert(root,4); 
	root = Insert(root,1); root = Insert(root,11);

	//Print Nodes in Inorder
	cout<<"Inorder Traversal: ";
	Inorder(root);
	cout<<"\n";

	// Find Inorder successor of some node. 
	struct Node* successor = Getsuccessor(root,1);
	if(successor == NULL) cout<<"No successor Found\n";
	else
    cout<<"Successor is "<<successor->data<<"\n";
}

A more simpler program in java which takes care of both the cases

public TreeNode getSuccessor(TreeNode a, int b) {
       TreeNode res=null;
       TreeNode cur=a;
       while(cur!=null){
           if(cur.val>b){
               res=cur;
               cur=cur.left;
            }else{
               cur=cur.right;
           }
       }
       return res;
   }

awesome

Line 54 should be like this : cout<<root->data<<" "; //Print data
Because we are in c++ right now :D

Hey Resul,
C++ supports backward compatibility from C, making it easier to use either of the syntaxes " cout<< " or printf(" %d ", root-> data ) .
Though, I agree each of these "print function to console" has different uses and applications.
Check this out for a better idea :
https://stackoverflow.com/questions/2872543/printf-vs-cout-in-c

Cheers.

` /* C++ program to find Inorder successor in a BST */
#include
using namespace std;
struct Node {
int data;
struct Node *left;
struct Node *right;
};

//Function to find some data in the tree
Node* Find(Node*root, int data) {
if(root == NULL) return NULL;
else if(root->data == data) return root;
else if(root->data < data) return Find(root->right,data);
else return Find(root->left,data);
}

//Function to find Node with maximum value in a BST
struct Node* FindMax(struct Node* root) {
if(root == NULL) return NULL;
while(root->right != NULL)
root = root->right;
return root;
}

//Function to find Inorder Predecessor in a BST
struct Node* Getpredecessor (struct Node* root,int data) {
// Search the Node - O(h)
struct Node* current = Find(root,data);
if(current == NULL) return NULL;
if(current->left != NULL) { //Case 1: Node has left subtree
return FindMax(current->left); // O(h)
}
else { //Case 2: No left subtree - O(h)
struct Node* predecessor = NULL;
struct Node* ancestor = root;
while(ancestor != current) {
if(current->data > ancestor->data) {
if(ancestor->data < current->data)
predecessor = ancestor; // so far this is the deepest node for which current node is in right

			  ancestor = ancestor->right;
		}
		else
              ancestor = ancestor->left;
	}
	return predecessor ;
}

}

//Function to visit nodes in Inorder
void Inorder(Node *root) {
if(root == NULL) return;

Inorder(root->left);       //Visit right subtree
printf("%d ",root->data);  //Print data
Inorder(root->right);      // Visit right subtree

}

//Function to visit nodes in Postorder
void Postorder(Node *root) {
if(root == NULL) return;

Postorder(root->right);       //Visit right subtree
printf("%d ",root->data);  //Print data
Postorder(root->left);      // Visit right subtree

}

// Function to Insert Node in a Binary Search Tree
Node* Insert(Node *root,char data) {
if(root == NULL) {
root = new Node();
root->data = data;
root->left = root->right = NULL;
}
else if(data <= root->data)
root->left = Insert(root->left,data);
else
root->right = Insert(root->right,data);
return root;
}

int main() {
/*Code To Test the logic
Creating an example tree
5
/
3 10
/ \
1 4 11
/
Node root = NULL;
root = Insert(root,5); root = Insert(root,10);
root = Insert(root,3); root = Insert(root,4);
root = Insert(root,1); root = Insert(root,11);

//Print Nodes in Inorder
cout<<"Postorder Traversal: ";
Postorder(root);
cout<<"\n";

// Find Inorder successor of some node. 
struct Node* predecessor = Getpredecessor(root,8);
if(predecessor == NULL) cout<<"No predecessor Found\n";
else
cout<<"Predecessor is "<<predecessor->data<<"\n";

}

i dont know if its good practice, but it a different faster implementation in trade off for higher memory requierements

Node* successor(Node * root, int data, Node * ancestor=NULL){
	//if found, return either right sub or ancestor
	if(root->data==data){
		if(root->right!=NULL)return root->right;
		else return ancestor;
	}
	// search for Node, if call for left sub, give self as arg
	if (data<root->data)return successor(root->left, data, root);
	else return successor(root->right, data, ancestor);
}