285. Inorder Successor in BST

Question

Given the root of a binary search tree and a node p in it, return the in-order successor of that node in the BST. If the given node has no in-order successor in the tree, return null.

The successor of a node p is the node with the smallest key greater than p.val.

Example 1:

Input: root = [2,1,3], p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.

Algorithm

A easy way to solve this problem is we follow the guidance of in-order traverse and keep the previous node until we find its the p. Then current node is the successor. Well this method will have a O(n) complexity due to the stack.

Another way is to utilize the tree attribute (left is smaller than root and right is larger). We start to loop the tree if the p.val is larger than root, then we go right to continue looking for the successor, if the p.val is smaller, root(cur node) may be the successor, we make it as potential result and go to left to continue looking for the successor. Loop the same process until hit the bottom(leaf).

For such questions, normally lazy or not cool way to solve it is traverse, and in the loop, we find or could do something. And better way to solve such question normally relies on the attributes of BST, like in-order traverse result is a ascending list, left is always smaller than root and right is lager.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode prev = null;
        if (root == null) return prev;
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        while (!stack.isEmpty()) {
            while (root.left != null) {
                stack.push(root.left);
                root = root.left;
            }
            TreeNode node = stack.pop();
            if (prev != null && prev.val == p.val) {
                return node;
            }
            prev = node;
            if (node.right != null) {
                root = node.right;
                stack.push(root);
            }
        }
        return null;
    }
}

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null) return root;
        TreeNode res = null;
        while (root != null) {
            if (root.val <= p.val) root = root.right;
            else {
                res = root;
                root = root.left;
            }
        }
        return res;
    }
}