Inorder Successor in BST
Problem
Given the root of a BST and a node p, return the in-order successor — the smallest node greater than p, or null.
root = [2,1,3], p = 12def inorder_successor(root, p):
succ = None
while root:
if root.val > p.val:
succ = root; root = root.left
else:
root = root.right
return succfunction inorderSuccessor(root, p) {
let succ = null;
while (root) {
if (root.val > p.val) { succ = root; root = root.left; }
else root = root.right;
}
return succ;
}class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode succ = null;
while (root != null) {
if (root.val > p.val) { succ = root; root = root.left; }
else root = root.right;
}
return succ;
}
}TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
TreeNode* succ = nullptr;
while (root) {
if (root->val > p->val) { succ = root; root = root->left; }
else root = root->right;
}
return succ;
}Explanation
The inorder successor of p is the smallest value in the BST that is still greater than p. Instead of doing a full traversal, we let the BST ordering guide a single top-to-bottom walk.
We keep a running succ candidate, starting at null. At each node, if its value is greater than p, it could be the successor, so we save it and move left to look for something even smaller that is still bigger than p. If its value is not greater than p, the answer must be larger, so we move right.
The trick is that the last node we record while going left is exactly the tightest upper bound, which is the successor. We never overwrite it with anything too large.
Example: root = [2,1,3], p = 1. At root 2, since 2 > 1 we set succ = 2 and go left to 1. At 1, 1 is not greater than 1, so we go right into emptiness. The loop ends and succ = 2 is returned.
Each step moves down one level, so the walk costs O(h) time and only O(1) extra space.