CareerCup

A basic inorder traversal can solve the problem as other posters have pointed out. But it is wasteful. In the case the target is in the right subtree of the root, traversing the whole left subtree is useless.

In fact, a modified binary search is more suitable here. Notice that

successor = the smallest node larger than target

Finding the first entry larger than target in a sorted array is a simple variation of binary search in a sorted array. Here we can use a similar idea for binary search in BST.

During the binary search in BST, there are two cases:

1. if currNode <= target, the successor must be in the right subtree. Continue the binary search in the right subtree.

2. if currNode > target, two possibilities here: successor is also in the left subtree, or currNode is the successor if target is the largest in the subtree. Memorize currNode as the candidate for successor. It will be overwritten if target is in the left subtree of some other node further down.

When return, pay attention to the two corner cases when the successor doesn't not exist:
1. target cannot be found in the tree;
2. target is the largest in the tree, so it has no inorder successor.

Here is my Java implementation.

public class inorderSuccessor {
	public static TreeNode iterativeSolution(TreeNode root, TreeNode target) {
		if (root == null || target == null) return null;
		boolean targetFound = false;
		TreeNode currNode = root, candidate=null;
		while (currNode != null) {
			if (currNode.val == target.val) {
				targetFound = true;
				currNode = currNode.right;
			}
			else if (currNode.val > target.val) {
				candidate = currNode;			
				currNode = currNode.left;
			}
			else {// currNode.val < target.val 
				currNode = currNode.right;
			}
		}
		return targetFound ? candidate : null;
	}
}

1.We can traverse tree in inorder manner.
2. We will have two pointers prev and current.
3.When prev is equal to the node given current pointer will b our answer.

Correct me If I m wrong.

directly walk thru the whole BST is not ideal.

One possible solution is this -

1. you check the given target node, and see if the node has a right child, if it has the successor is the most left element in the right child tree (let me know if you can't understand this part.)

2. if the given target node doesn't have a right child, means you need to figure out the element that is just bigger than the target, because the target has no right child, it can tell that by itself, so what to do next is to utilize and walk thru the BST , keep a track of the most recent element that is bigger than the target element until we find the element.
Return Null if such element doesn't exist.

Node FindInOrderSuccessorBST(node root, node targetNode)
{
	If (targetNode == null || root == null) return null; 
	
	// if the target has a right child. The successor is the most left child in right child tree. 
	If (targetNode.Right != null)
	{
		Return FindMostLeftNode(targetNode.Right); 
	}

	// if the target has no right child. We do a search for the target Node in the BST and keep tracking for the last found element that is bigger than the target element, if such element exists it is the successor of the target , otherwise return null. 
	
	Return GetLastBiggerElement(root,targetNode); 
}


Node GetLastBiggerElement(node root, node targetNode)
{
	If (root != null) {
	If (root.value > targetNode.value)
	{
		Return root.Left == null ? Root : GetlastBiggerElement(root.Left,targetNode) ?? Root;
	}
	
	If (root .value < targetNode.value)
	{
		Get:LastBiggerElement(Root.Right) ;
	}
	}
	
	Return null; // root is null or we found the element. 
}

Node FindMostLeftNode (node Root)
{
	If (root == null) return null; 
	Return Root.Left != null FindMostLeftNode(Root.Left) : Root;
}

find a node with a given value, keeping track of parent too

y=0;
x=root;
z = 0;
while( x != 0 && x->value != value )
{
	y = x;
	if( x -> value < value )
		x = x->right; // value is in right subtree of x
	else
	{
		z = x;
		x = x->left; // value is in left subtree of x
	}
}

Now having x and y with x pointing to given value and y pointing to parent.

Inorder successor will be smallest in right subtree of x. If x has no right subtree then if x is either left child of y , in which case y is next highest value after x. If x is however a right child, then return to root and start finding x->data again, wherever you took left turn last is successor, thats z

if( x->right != 0 )
	return minimum(x->right); 
if(x == y->left )
	return y;
return z;

NODE * inorder_successor(NODE *p, NODE *nodeToBeSearched)
{
	static bool found =0;
	if (p == NULL)
		return NULL;
	else
	{
        if (p == nodeToBeSearched) {
            return p;
        }
        else
        {
            NODE *nodefound = inorder_successor(p->left, nodeToBeSearched);
            if (nodefound != NULL) {
                if (!found) {
                    found = 1;
                    return p;
                }
                else
                    return nodefound;
            }
            else
            {
                return inorder_successor(p->right, nodeToBeSearched);
            }
        }
    }
}