#285 Inorder Successor in BST
the problem
In plain words
You get the root of a BST with distinct values and a node p that lives in it. Return the node that comes right after p when the tree is read in sorted (inorder) order — that is, the node with the smallest value bigger than p.val. If p holds the largest value, return null.
in root = [20,10,30,5,15], p = 10
out 15
10 has a right subtree; its smallest value, 15, comes next.
in root = [20,10,30,5,15], p = 15
out 20
15 has no right subtree; the next value is the ancestor where the path to 15 last turned left.
in root = [20,10,30,5,15], p = 30
out null
30 is the largest value.
- 1 ≤ number of nodes ≤ 10⁴
- -10⁵ ≤ Node.val ≤ 10⁵
- All values are distinct
- p is a node of the tree
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code right here. Stuck for 20 minutes? Open one hint at a time.
This one is LeetCode Premium. You don't need a subscription: solve it right here. The free alternative linked above is the closest free practice; its label says how close it is.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBST property
Every node bigger than p is a candidate, and as you walk down from the root each new candidate is closer to p. Bigger → remember it and go left; not bigger → go right. The last candidate wins.
solutions
From brute force to optimal
List all nodes in sorted order, find p, return the node after it.
- Inorder traversal into a list of nodes.
- Find p in the list.
- Return the next node, or null if p is last.
Visits every node once.
The list of all nodes (plus O(h) recursion).
class Solution { /** Inorder of a BST is sorted: list the nodes in order, find p, return the node after it. */ public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { List<TreeNode> order = new ArrayList<>(); collect(root, order); for (int i = 0; i + 1 < order.size(); i++) { if (order.get(i) == p) return order.get(i + 1); // the very next node in sorted order } return null; // p holds the largest value } private void collect(TreeNode node, List<TreeNode> out) { if (node == null) return; collect(node.left, out); out.add(node); collect(node.right, out); }}A ceiling-style search for the smallest value > p.val.
- successor = null, cur = root.
- p.val < cur.val → successor = cur, go left.
- Otherwise go right.
- When cur falls off the tree, return successor.
One node per level: O(log n) balanced, O(n) skewed.
Two pointers.
class Solution { public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { TreeNode successor = null; // smallest value > p.val seen so far TreeNode cur = root; while (cur != null) { if (p.val < cur.val) { successor = cur; // bigger than p: a candidate cur = cur.left; // a smaller candidate can only be on the left } else { cur = cur.right; // cur ≤ p: everything bigger is on the right } } return successor; // the last candidate is the closest one }}Dry run
The textbook view: if p has a right subtree, the answer is its leftmost node; otherwise it's the last ancestor where the path to p turned left.
- p.right != null → walk left from p.right to the end.
- Else walk from the root to p, remembering every node where you went left.
- Return the last one remembered (or null).
Either a walk down p's right subtree or one walk from the root to p.
A couple of pointers.
class Solution { public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { if (p.right != null) { // case 1: leftmost node of p's right subtree TreeNode cur = p.right; while (cur.left != null) cur = cur.left; return cur; } TreeNode successor = null; // case 2: the last node where the path to p turned left TreeNode cur = root; while (cur != p) { if (p.val < cur.val) { successor = cur; cur = cur.left; } else { cur = cur.right; } } return successor; }}in the room
How to say it in the interview
talk track
- Define it first: "the successor is the smallest value bigger than p.val" — then the walk follows naturally.
- Explain why the last candidate wins: after a candidate we only go left, into values that are smaller but still bigger than p.
- Give O(h) time, O(1) space; mention that with a TreeMap it's just
higherKey(p.val).
traps
- Returning the first node bigger than p — it's usually too big; keep walking left.
- Comparing nodes by value with
==onIntegerobjects; compareintfields, or compare node references. - Forgetting the null case when p holds the largest value.
what they ask next
Follow-ups
Inorder predecessor?
Mirror it: a node smaller than p is a candidate — remember it and go right; otherwise go left.
Inorder Successor in BST II (LC 510) — each node also has a parent pointer, and you don't get the root?
If p has a right subtree, take its leftmost node. Otherwise climb parents until you come up from a left child; that parent is the answer (or null).
before you submit
Edge cases to test
- p holds the largest value → null.
- p has a right subtree → the answer is that subtree's leftmost node.
- p has no right subtree → the answer is the last ancestor where the path to p turned left.
- A skewed tree of 2000 nodes → the walk is 2000 steps but still O(1) extra space.
practise next
Similar problems
- #173Binary Search Tree IteratorMediumin BST
- #450Delete Node in a BSTMediumin BST
- #700Search in a Binary Search TreeEasyin BST