Reference: LeetCode
Difficulty: Medium

My Post: Java Solution + Explanation (Recursion & Iteration)

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.

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.

Example: 

1
2
3
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.

Analysis

Methods:

x is the current node; p is the target node.

  1. Recursion
    • If p is in the left subtree, the successor could be x or successor(x.left). It means that x is a possible candidate. It turns to be a real successor when the return value of successor(x.left) equals null.
    • If p is in the right subtree, the successor must be in the right subtree if it exists.
    • If p is found, we still go to right subtree to find its successor if it exists.
    • The base case is when x reaches null.
    • Time: $O(h)$
    • Space: $O(h)$
  2. Iteration
    • We use a variable succ to record the successor, which is initially null.
    • If p.val is less than x.val, it needs to go left, and we need to update succ.
    • If p.val is greater than or equal to x.val:
      • greater than: Just go right. x.left and x couldn’t be the successor.
      • equal to: Just go right too. In the next round, p.val will be less than x.val, it will set the succ to the would-be right child x.
    • Time: $O(h)$
    • Space: $O(1)$

Code

Test Case:

1
2
3
4
[2,1,3]    p = 1
3
[2,null,3] p = 2
3

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
  if (p == null) return null;
  return successor(root, p);
}

private TreeNode successor(TreeNode x, TreeNode p) {
  if (x == null) {
    return null;
  }
  if (p.val < x.val) { // go left
    TreeNode succ = successor(x.left, p); // try to find successor
    return (succ == null) ? x : succ;
  } else {             // p.val >= x.val
    return successor(x.right, p);
  }
}

Predecessor:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public TreeNode inorderPredecessor(TreeNode root, TreeNode p) {
  if (p == null) return null;
  return predecessor(root, p);
}

private TreeNode predecessor(TreeNode x, TreeNode p) {
  if (x == null) {
    return null;
  }
  if (p.val > x.val) {
    TreeNode pred = predecessor(x.right, p);
    return (pred == null) ? x : pred;
  } else {
    return predecessor(x.left, p);
  }
}

Iteration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
  if (root == null || p == null) return null;
  
  TreeNode x = root;
  TreeNode succ = null;
  while (x != null) {    // p.val is the key
    if (p.val < x.val) { // go left
      succ = x;          // update successor
      x = x.left;
    } else {             // go right
      x = x.right;
    }
  }
  return succ;
}

Ceil

Code: algs4 - BST.java

The idea is also applied to ceil operation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public Key ceil(Key key) {
  Node x = ceil(root, key);
  if (x == null) throw new NoSuchElementException();
  return x.key;
}

private Node ceil(Node x, Key key) {
  if (x == null) return null;
  int cmp = key.compareTo(x.key);
  if (cmp < 0) { // left
    Node ret = ceil(x.right, key);
    if (ret == null) return x; // does not exist
    else return ret;
  } else if (cmp > 0) {
    return ceil(x.left, key);    
  } else { // equal => return itself
    return x;
  }
}