Watch 10 video solutions for Inorder Successor in BST, a medium level problem involving Tree, Depth-First Search, Binary Search Tree. This walkthrough by mycodeschool has 366,995 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem 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. Inorder traversal of a BST processes nodes in sorted order, so the successor is the smallest value greater than p.val.
Approach 1: Full Inorder Traversal (DFS) (O(n) time, O(n) space)
Run a complete inorder traversal using recursion or an explicit stack and store nodes in a list. Since inorder traversal of a BST yields values in ascending order, iterate through the list and return the element that comes immediately after p. This method uses Depth-First Search and works for any Binary Tree, not just BSTs. The downside is extra memory to store the traversal and unnecessary work when the successor appears early.
Approach 2: Iterative Inorder with Early Stop (O(n) time, O(h) space)
Perform an inorder traversal using a stack but stop as soon as you process node p. Track the previously visited node during traversal. Once p is visited, the very next node popped from the stack is the successor. This reduces memory usage compared to storing the entire traversal while still using the standard DFS traversal pattern. Time complexity remains O(n) in the worst case because you may still traverse most of the tree.
Approach 3: Use BST Property (Optimal) (O(h) time, O(1) space)
A Binary Search Tree gives a stronger guarantee: left subtree values are smaller and right subtree values are larger. Traverse from the root and maintain a candidate successor. If p.val is less than the current node's value, that node could be the successor, so store it and move left to search for a smaller valid candidate. If p.val is greater than or equal to the current node's value, move right because the successor must be larger. This greedy search walks down a single path of the tree, giving O(h) time where h is the tree height and constant extra space.
Recommended for interviews: Start by explaining the inorder traversal property of BSTs. Mention the O(n) DFS traversal as a baseline to show understanding. Then optimize using the BST ordering rule to achieve O(h) time and O(1) space. Interviewers typically expect the BST-property solution because it demonstrates that you recognize and exploit structure instead of treating the tree as a generic binary tree.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Full Inorder Traversal (Store Array) | O(n) | O(n) | Simple baseline solution or when tree is not guaranteed to be a BST |
| Iterative Inorder with Stack | O(n) | O(h) | When you want DFS traversal without storing the full list |
| BST Property Search (Optimal) | O(h) | O(1) | Best choice when the input is a Binary Search Tree |
