On this page

Inorder Successor in Bst

Given the root of a BST and a node p in it, return the in-order successor of p: the node with the smallest value greater than p.val. If p has no successor, return null.

Constraints:

  • The number of nodes is in the range [1, 10^4].
  • All values are unique and p is a node of the tree.

Intuition

1 8
2 / \
3 4 12
4 / \ / \
5 2 6 10 14

The sorted order is 2, 4, 6, 8, 10, 12, 14. The successor of 6 is 8, of 4 is 6, and of 14 is null.

The successor is the smallest value strictly greater than p. That is exactly the ceil idea from earlier, with a strict comparison:

  • If the current node is greater than p, it is a candidate. A smaller candidate might be in its left subtree, so remember it and go left.
  • If the current node is less than or equal to p, it and its left subtree are too small, so go right.

Approach: Walk Down and Remember the Candidate

  1. Set successor = null.
  2. While the node exists:
    • If p.val >= node.val, go right.
    • Otherwise set successor = node and go left.
  3. Return successor.

This works whether or not p has a right subtree, so no special cases are needed. (The alternative case analysis is: if p has a right child, the answer is the leftmost node of that subtree; otherwise it is the nearest ancestor for which p lies in the left subtree. The walk above finds exactly that.)

Code

class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
TreeNode* successor = nullptr;
while (root != nullptr) {
if (p->val >= root->val) {
root = root->right;
} else {
successor = root;
root = root->left;
}
}
return successor;
}
};

Complexity

Time: O(h)

One root-to-leaf path is walked: O(log n) balanced, O(n) skewed.

Space: O(1)

Only one extra pointer is kept.

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"The in-order successor is the smallest value strictly greater than p, so it is the ceil idea with a strict comparison. I walk down from the root with a stored candidate. If p's value is greater than or equal to the current node, that node and everything to its left are too small, so I go right. Otherwise the current node is greater than p, so it is a candidate, and I store it and go left to look for a smaller one. When I fall off the tree, the stored candidate is the successor, or null if none was found. It never needs the parent pointers, takes O of h time, and uses O of one space."
Next TopicInorder Predecessor in BST