CareerCup

Using recursion it can be done as follows:

public static Tree InorderSuccessor(int value, Tree root, ref Tree caller, ref Tree successor)
{
if (root != null)
{
InorderSuccessor(value,root.Left, ref root, ref successor);
if (root.Data == value)
successor = caller;
InorderSuccessor(value, root.Right, ref root, ref successor);

}

return successor;


}

So the idea is to traverse the tree in in-order format. The caller of the function will always be the successor.
When you call from main the call will look like this

Tree succ = null;
int value; assing this to the value of node for which you need the successor for.
succ = InorderSuccessor(value,root, ref succ, ref succ);

I have provided the successor method as a part of class Tree below.

class node{
public:
int key;
node* left;
node* right;
node(int key) {
this->key = key;
left = right = 0;
}
};

class Tree{
node* root;

public:
Tree(node *p):root(p) {}
void addNode(int key) {
node *p = new node(key);
addNode(p);
}

node* find(int key) {
node* curr = root;
while(curr) {
if (curr->key == key) {
return curr;
}
if (curr->key < key) {
curr = curr->right;
} else {
curr = curr->left;
}
}

return NULL;
}

node* succussor(int key) {
node *p = find(key);
if(!p) {
cout<<"Cannot find "<<key<<endl;
return NULL;
}
if (p->right) { //Go one right and then left all the way till end
p = p->right;
for(;p->left;p=p->left);
return p;
} else { //successor the "nearest" ancestor to node p such that p is in the left
//subtree of the successor
node *curr = root,*successor = 0;
while(curr) {
if (curr->key == p->key) {
if (!successor) cout<<key<<" doesn't have any successor!"<<endl;
return successor;
}
if (curr->key < p->key) {
curr = curr->right;
} else {
successor = curr;
curr = curr->left;
}
}
}
}
};

Solution: Exploit Binary Search Algorithm such that when key is found on node N,
a) if N has a right sub tree -- the leftmost node is the successor
b) if N does not has --> simply mark isFound (optional, not needed when we are guarantee the key is always found in the tree)
c) for the earliest ancestor of N where the left sub tree contains key (isFound but succ is null) --> it is the successor.

global isFound = false;

Node getSuccessor(Node root, int key){
	//base case
	if(root.val == key ){
		isFound = true;
		if(root.right != null) 
			return getLeftMost(root.right);
		else
			return null;
	}	
	//recursive
	Node succ;
	if(root.val > key){
		succ = getSuccessor(root.left, key);
		if(isFound && succ == null) succ = root; 
	}else{
		succ = getSuccessor(root.right, key);
	}
	return succ;
}