285. Inorder Successor in BST (Medium)

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, returnnull.

    4
   / \
  2   5
 / \
1   3

Solution 1: O(h); O(1)

The inorder traversal of a BST is the nodes in ascending order. To find the inorder successor, we just need to find the smallest one that is larger than the given value since there are no duplicate values in a BST.

    /**
     * Solution 1: O(h); O(1)
     * Set root node as current node and then Search BST.
     * While current node is not null, if the value of current node > the value of target node,
     * update result to current node and move current node to left, otherwise right.
     */
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode res = null;
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val > p.val) { //possible Inorder Successor
                res = cur;
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        return res;
    }