Iterative & Recursive Java Solution with Detailed Explanation


  • 3
    Y

    Iterative version:
    The problem is equivalent to finding the first (smallest) element greater than p in the BST. There are 3 cases to consider:

    1. p has a right child, then the inorder successor is the left most leaf of the right child.
    2. p doesn't have a right child, there are 2 cases:
      a) p is the largest value in the BST and there is no inorder successor.
      b) There are nodes at upper levels with values > p, and we need to find the smallest of those.
      We can combine 2a and 2b together. Use a temporary TreeNode cur to traverse the tree. If cur <= p, go right to find nodes > p. Else if cur > p, store cur, and go left to find smaller nodes > p. We stop when we reach p. The last stored cur (smallest among nodes > p) is our answer. If cur is null, then we can't find a node > p, and there is no inorder successor.
    public class Solution {
        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            if (root == null) return null;
            if (p.right != null) {
                TreeNode cur = p.right;
                while (cur.left != null) {
                    cur = cur.left;
                }
                return cur;
            } else {
                TreeNode cur = root, prev = null;
                while (cur != p) {
                    if (cur.val > p.val) {
                        prev = cur;
                        cur = cur.left;
                    } else if (cur.val < p.val) {
                        cur = cur.right;
                    }
                }
                return prev;
            }
        }
    }
    // O(Log(n)) time, O(1) space
    

    The code above can be boiled down to a shorter one by combining case 1 & 2 above. Start from root and traverse down the BST.

    1. If cur.val > p.val, store cur (update it if we have smaller values > p), then it can be two cases:
      a) cur is an ancestor of p with value > p --> go left to find smaller values > p
      b) cur is in right subtree of p (actually must be a right child of p) --> go left to find smaller values > p
    2. If cur.val <= p.val, it can be:
      a) cur == p --> go right to find values > p
      b) cur is an ancestor of p with value < p --> go right to find values > p
    public class Solution {
        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            TreeNode cur = root, prev = null;
            while (cur != null) {
                if (cur.val > p.val) {
                    prev = cur;
                    cur = cur.left;
                } else {
                    cur = cur.right;
                }
            }
            return prev;
        }
    }
    

    Recursive version (same idea): if root.val <= p.val, then the inorder successor must be in the right subtree. Else if root.val > p.val, the inorder successor could be current root, or some smaller value inside the left subtree.

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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.