Inorder Successor in BST
Return the node with the smallest value greater than p.val, or null.
02
Intuition
Successor = ceiling of p.val, exclusive. Walk from the root: going left past a node means that node is a successor candidate (it's bigger); going right discards. No parent pointers needed.
03
Approach
1
Candidate on left turns
node.val > p.val → node might be the successor; remember it and go left for something tighter.
2
Discard on right turns
node.val ≤ p.val → successor must be right of here.
3
Classic alternative
If p has a right subtree, the successor is that subtree's leftmost node — the walk above covers both cases uniformly.
04
Solution & live demo
python
▶1class Solution:
▶2 def inorderSuccessor(self, root, p):
▶3 succ = None
▶4 node = root
▶5 while node:
▶6 if node.val > p.val:
▶7 succ = node # candidate, try tighter
▶8 node = node.left
▶9 else:
▶10 node = node.right
▶11 return succ
05
Edge cases
p is the maximum
No left turn ever recorded → None.
Duplicates
Strict > comparison skips equal values correctly.
06
Complexity
Time
O(h)
Space
O(1)
One descent from the root.