Write a program to do a find inorder successor of a binary search tree

     6
   /  \
  3    10
 / \   / \
1   4 7   8
     \
      5 	 
Consider inorder traversal
1,3,4,5,6,7,10,8
The inorder successor of 1 is 3, 5 is 6, 7 is 10.

The trick to find the inorder is to do inorder traversal and find the next elemnt which comes in the traversal. But it is not required to traverse the tree completely. Here is the algorithm:

1) If the node has right child, the leftmost child of the node will be the successor.

2) If node doesn't have a right child, the successor is one of the first ancestor which is bigger than the node.

public class InorderSuccessor {
	public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
		if (root == null)
			return null;

		if (root.val <= p.val) {
			return inorderSuccessor(root.right, p);
		} else {
			TreeNode left = inorderSuccessor(root.left, p);
			return (left != null) ? left : root;
		}
	}

	class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}
}