Reference: LeetCode EPI 9.9
Difficulty: Medium

Note: EPI 9.9 does not assume that the tree is a BST, which means we don’t use values.

Problem

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

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

You will have direct access to the node but not to the root of the tree. Each node will have a reference to its parent node.

Note:

  • If the given node has no in-order successor in the tree, return null.
  • It’s guaranteed that the values of the tree are unique.
  • Remember that we are using the Node type instead of TreeNode type so their string representation are different.

Follow up: Could you solve it without looking up any of the node’s values?

Analysis

Methods:

  1. Brute-Force (Value-based)
    • Since it is BST, we do inorder traversal. Return the node after the target node x.
    • But you have to use parent links to find the root first.
    • Time: $O(h)$
    • Space: $O(1)$
  2. Iteration
    • If the node has a right child, and hence its successor is somewhere lower in the tree. Go to the right once and then as many times to the left as you could. Return the node you end up with.
    • Node has no right child, and hence its successor is somewhere upper in the tree. Go up till the node that is left child of its parent. The answer is the parent.
    • Time: $O(h)$
    • Space: $O(1)$

Code

Iteration

Note:

  • Base case checking matters here, since it uses x.right.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public Node inorderSuccessor(Node x) {
  if (x == null) {
    return null;
  }
  
  // x has right child
  if (x.right != null) {
    x = x.right;
    while (x.left != null) {
      x = x.left; // go to the leftmost node
    }
    return x;
  }
  
  // x has no right child
  while (x.parent != null) {
    if (x.parent.left == x) {
      return x.parent;
    }
    x = x.parent;
  }
  
  return null;  // it is the last node in the inorder list
}