Inorder Successor in BST
Return the node that comes right after p in an inorder traversal of a binary search tree, the smallest value larger than p, using one walk down from the root.
Problem Understanding
Inorder Successor in BST (LeetCode 285): given the root of a binary search tree and a node p in it, return the node visited right after p in an inorder traversal, or null if p is last. In a BST that is the node with the smallest value larger than p.val.
Examples: root = [2,1,3], p = 1 → 2; root = [5,3,6,2,4,null,null,1], p = 6 → null.
The Intuition: Binary Search for "Just Larger"
This is a binary search on the tree for the first value greater than p:
- Node larger than p: it is a possible answer. Remember it, then look left for something smaller that still beats
p. - Node not larger: it and everything on its left are too small. Go right.
- Fall off the tree: the last remembered node is the smallest value larger than
p.
The walk is the same one as Insert into a Binary Search Tree, and the full inorder order it shortcuts is drawn in Binary Tree Inorder Traversal.
Interactive Walkthrough
p = 6 · GREEN = BEST CANDIDATE
START AT ROOT
p
6
candidate
:
answer
:
Find the smallest value larger than 6. No candidate yet; start at the root 8
Next
6 < 8: 8 is the best successor so far; look left for a smaller one
BST
p
The green node is the best candidate so far; it changes only when the walk turns left. Try Right subtree to see the candidate move down into p's right subtree.
Dry Run Table
Input: root = [8,4,10,2,6], p = 6.
| Node | Compare | Candidate | Move |
|---|---|---|---|
| 8 | 6 < 8 | 8 | left |
| 4 | 6 > 4 | 8 | right |
| 6 | p itself | 8 | right (empty) |
Answer: 8. p has no right subtree, so its successor is the ancestor it sits under on the left.
The Solution Template
One loop, one remembered node.
Inorder Successor in BST Code
1var inorderSuccessor = function(root, p) {2 let successor = null;3 let node = root;4 while (node) {5 if (p.val < node.val) {6 successor = node;7 node = node.left;8 } else {9 node = node.right;10 }11 }12 return successor;13};
Edge Cases & Common Mistakes
- p is the maximum: never turn left, return null.
- Using <= instead of <: p itself would become the candidate and the answer would be p.
- Only checking p's right subtree: misses the case where the successor is an ancestor.
- Full inorder traversal: correct but O(n) time and space; the walk is O(h) and O(1).
- Skewed tree: h can be n, so the worst case is still O(n).
Summary
Walk down from the root; whenever p is smaller than the node, record the node and go left, otherwise go right. The last recorded node is the successor. O(h) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet