The next value up
Find the smallest value in a search tree that is larger than a given value, by walking down once and remembering the last node where you turned left. About 12 minutes.
Candidates on the way down
The successor of a value p is the smallest value in the tree that is bigger than p. Start at the root and walk down as in a search.
If the current node is bigger than p, it could be the answer, so remember it. But a smaller candidate might hide on its left, so go left. If the current node is not bigger than p, nothing in its left part can be bigger, so go right.
if node.val > p:
succ = node.val
node = node.left
else:
node = node.right- candidate
- 5
At 5: bigger than 4. Remember 5 and go left.
When there is none
If no node along the way is bigger than p, the answer was never set. That happens when p is the largest value in the tree. Start the answer at minus one, which the problem defines as no successor.
The value p itself need not be in the tree for this walk to work, and the walk ends when it falls off the bottom. No recursion and no extra memory are needed.
succ = -1 ... return succ
At a node whose value equals p, which way do you go?
- ARight, since the successor must be strictly larger
- BLeft, to find smaller values
- CStop, the node is the answer
Show the answer
Right, since the successor must be strictly larger. Nothing on the left, or the node itself, can exceed p.
Inorder successor in a search tree
Given the root of a binary search tree with different values and an integer p, return the smallest value in the tree that is strictly greater than p, or -1 if there is none. The value p need not be in the tree.
root = [5, 3, 6, 2, 4, null, 7], p = 4 → 5
0 ≤ number of nodes ≤ 10,000 · -100,000 ≤ node.val, p ≤ 100,000