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
pis a node of the tree.
Intuition
1 82 / \3 4 124 / \ / \5 2 6 10 14The 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
- Set
successor = null. - While the node exists:
- If
p.val >= node.val, go right. - Otherwise set
successor = nodeand go left.
- If
- 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
One root-to-leaf path is walked: O(log n) balanced, O(n) skewed.
Only one extra pointer is kept.