Watch 10 video solutions for Inorder Successor in BST, a medium level problem involving Tree, Depth-First Search, Binary Search Tree. This walkthrough by Cracking FAANG has 7,209 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the root of a binary search tree and a node p in it, return the in-order successor of that node in the BST. If the given node has no in-order successor in the tree, return null.
The successor of a node p is the node with the smallest key greater than p.val.
Example 1:
Input: root = [2,1,3], p = 1 Output: 2 Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.
Example 2:
Input: root = [5,3,6,2,4,null,null,1], p = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.
Constraints:
[1, 104].-105 <= Node.val <= 105Problem Overview: Given the root of a Binary Search Tree and a node p, return the node that appears immediately after p in an inorder traversal. The inorder successor is the smallest value strictly greater than p.val.
Approach 1: Inorder Traversal (DFS) (Time: O(n), Space: O(n))
The straightforward solution performs a full inorder traversal of the tree using depth-first search. Inorder traversal of a binary search tree produces values in sorted order. Store nodes in a list while traversing left → root → right. Once traversal completes, iterate through the list to find node p and return the next element. This approach is simple and works for any binary tree, but it uses extra memory to store all nodes and always scans the entire tree even when the successor is near the root.
Approach 2: Binary Search Using BST Property (Time: O(h), Space: O(1))
A Binary Search Tree gives a stronger guarantee: left subtree values are smaller than the node, and right subtree values are larger. Use this ordering to search for the successor without traversing every node. Start at the root and keep a candidate successor. If p.val is smaller than the current node's value, the current node could be the successor, so store it and move left to find a smaller valid candidate. If p.val is greater than or equal to the current node's value, move right since any successor must be larger. Continue until reaching a null node. The stored candidate is the inorder successor.
This approach effectively performs a guided binary search through the BST. The runtime depends on the tree height h, which is O(log n) for balanced trees and O(n) in the worst case of a skewed tree. It avoids extra memory because it only keeps a pointer to the best candidate seen so far.
Recommended for interviews: Interviewers typically expect the BST binary search approach. Starting with the inorder traversal shows you understand what “inorder successor” means, but the optimized solution demonstrates that you can leverage the structural guarantees of a Binary Search Tree to reduce the search to O(h) time with constant space.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Inorder Traversal (DFS) | O(n) | O(n) | Simple baseline approach or when BST properties are not leveraged |
| Binary Search Using BST Property | O(h) | O(1) | Optimal solution for Binary Search Trees; efficient when tree height is small |