DSA problem
Inorder Successor in BST
Given the root of a binary search tree and a node p in it, return the in-order successor of p in the BST. If p has no in-order successor, return null.
The in-order successor of a node p is the node with the smallest value greater than p.val. In an in-order traversal of a BST (which produces values in sorted order), the successor is simply the node that comes immediately after p.
A clean but unnecessarily expensive solution performs a full in-order traversal, collects the nodes into a list, finds p in the list, and returns the next entry. That takes O(n) time and space.
The optimal approach exploits the BST ordering directly, without needing access to parent pointers. Walk from the root: whenever node.val > p.val, this node could be the successor — record it as the current candidate and descend left to find an even smaller value above p.val. Whenever node.val <= p.val, descend right because everything in the left subtree is too small. When you fall off the tree, the most recently recorded candidate is the answer, or null if no candidate was ever set. This runs in O(h) time and O(1) extra space.
Examples
root = [2,1,3], p = 12root = [5,3,6,2,4,null,null,1], p = 6nullroot = [5,3,6,2,4,null,null,1], p = 45Constraints
- The number of nodes in the tree is in the range [1, 10^4].
- -10^5 <= Node.val <= 10^5
- All Nodes will have unique values.
- p is guaranteed to be a node in the tree.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.