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;
}
}

Comment