285. Inorder Successor in BST

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.

Solution:

Since the tree is BST, we know any node smaller than root is in its left subtree and any node larger than root is in its right subtree.

Therefore, if we find p.val < root.val, we know if we want to find p we should go left. So we set root to be the candidate of its successor and go left.

If p.val > root.val, since we're doing a in-order traversal, we do not need to update the successor.



Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null) {
            return root;
        }
        
        TreeNode succ = null;
        while (root != null) {
            if (root.val > p.val) {
                succ = root;
                root = root.left;
            }
            else {
                root = root.right;
            }
        }
        return succ;
    }
}