Inorder Successor in BST

Problem Description:

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

解题思路： 分2种情况：

• p有右子树，then its successor is just the leftmost child of its right subtree;
• p没有右子树，then a traversal is needed to find its successor.

public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    TreeNode successor = null;

    //p has right child
    if(p.right != null) {
        successor = p.right;
        while(successor.left != null)
            successor = successor.left;

            return successor;
    }

    while(root != null) {
        if(p.data < root.data) {
            successor = root;
            root = root.left;
        } else if(p.data > root.data) {
          root = root.right;
        } else {
          break;
        }
    }

    return successor;
}