Inorder Successor in BST
Inorder Successor in BST: return the node with the smallest value greater than p.val, or null.
- 1 <= number of nodes <= 10⁵
- -10⁹ <= node value <= 10⁹
- All values are distinct; return null when p holds the maximum
Intuition
The inorder successor in BST of a node p is the node with the smallest value strictly greater than p.val — the value that would come immediately after it if you listed the tree in sorted order.
The textbook framing splits into two cases. If p has a right subtree, the successor is the leftmost node of that subtree: the smallest value still larger than p. If it does not, the successor is the nearest ancestor from which p lies in the left subtree — which normally means walking up through parent pointers.
But you can avoid that case split entirely, and avoid needing parent pointers at all, by starting at the root instead. Walk downward comparing each node against p.val:
- A node greater than p.val is a possible successor — record it, then go left to look for something even closer.
- A node less than or equal to p.val cannot be the successor, so discard it and go right.
The recorded candidate only ever tightens as you descend, so whatever survives when you fall off the tree is the answer. This is the same walk as finding the ceiling of a value, with one difference: the comparison is strict, because the successor must be greater than p.val and never equal to it.
The successor is the smallest value strictly greater than p — which is the ceil question in disguise. That's why no in-order traversal is needed: the BST ordering already tells you that going left tightens an upper bound. Recognising a problem as "nearest neighbour on one side" collapses it to a single O(h) walk.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(h) time and O(1) space.
Start at the root with an empty candidate
Set successor = null and point a cursor at the root. Starting from the top rather than from p is what removes the need for parent pointers, and it handles both textbook cases with one loop.
Record and go left when the node is larger
If node.val > p.val, this node is a valid successor — save it — but a closer one may sit in its left subtree, so move left. Returning immediately here is the classic mistake; the saved candidate is what protects you if the left subtree holds nothing better.
Go right when the node is too small
If node.val <= p.val, neither this node nor anything in its left subtree can be the successor, since all those values are even smaller. Discard the whole left side and move right. Note the <=: equality is excluded because the successor must be strictly greater.
Return the last recorded candidate
The loop ends when the cursor becomes null. Return successor, which holds the tightest value found, or null if p holds the maximum value in the tree and no successor exists.
Relate it to the right-subtree rule
When p has a right subtree, this walk naturally descends into it and finds its leftmost node. When p does not, the walk records the ancestor it turned left at. One loop covers both cases, which is why it is worth preferring over the two-case version.
Cost is the height of the tree
Each iteration moves down one level, giving O(h) time — O(log n) balanced, O(n) for a degenerate chain — and O(1) space, since only a cursor and one candidate are stored.
Solution & live demo
Common pitfalls
Doing a full in-order traversal and taking the next node
vals = inorder(root) i = vals.index(p.val) return vals[i + 1]
while node:
if node.val > p.val:
succ = node
node = node.left
else:
node = node.rightCorrect, but O(n) time and O(n) space to answer a question the tree's shape already encodes. The walk is O(h) and allocates nothing.
Only looking inside p's right subtree
node = p.right while node.left: node = node.left return node
node = root
while node:
if node.val > p.val:
succ = node; node = node.left
else:
node = node.rightThat handles only the case where p has a right child. When it doesn't, the successor is an ancestor — the last node you turned left at — and this version returns nothing or crashes. Walking from the root covers both cases with no branching.
Edge cases
No left turn ever recorded → None.
Strict > comparison skips equal values correctly.