252. Inorder Successor in BST
You are given the root of a binary search tree and an integer target — the value of a node that is guaranteed to exist in the tree. Return the node that comes immediately after the target node in an inorder (ascending) traversal, called its in-order successor, or null if the target holds the largest value in the tree.
Put differently: among all nodes whose value is strictly greater than target, return the one with the smallest value.
All node values are distinct. A full traversal works, but the BST ordering lets you find the answer along a single root-to-leaf path.
Example 1:
Input: root = [2, 1, 3], target = 1
Output: TreeNode(2)
Explanation: Inorder order is 1, 2, 3. The node right after 1 is 2.
Example 2:
Input: root = [5, 3, 6, 2, 4, null, null, 1], target = 4
Output: TreeNode(5)
Explanation: Inorder order is 1, 2, 3, 4, 5, 6, so the successor of 4 is the root, 5 — an ancestor, not a descendant.
Constraints:
- 1 ≤ number of nodes ≤ 10⁴
- -10⁵ ≤ node values ≤ 10⁵
- All node values are distinct.
- target is the value of an existing node.
Hints:
An inorder traversal of a BST visits values in ascending order. Traverse, and return the node you visit right after seeing the target — O(n), but it ignores the BST property until the very end.
The successor is the smallest value greater than target. Walk down from the root: whenever a node's value is greater than target it is a *candidate* — remember it and go left to look for something smaller-but-still-greater; otherwise go right. The last candidate recorded is the answer, in O(h) with no stack.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [2, 1, 3], target = 1
Expected output: TreeNode(2)