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.
The in-order traversal of a binary search tree is an ascending sequence, so we can use the binary search method.
The in-order successor node of a binary search tree node p satisfies:
p.p.Therefore, for the current node root, if root.val > p.val, then root could be the in-order successor of p. We record root as ans and then search the left subtree, i.e., root = root.left. If root.val leq p.val, then root cannot be the in-order successor of p, and we search the right subtree, i.e., root = root.right.
The time complexity is O(h), where h is the height of the binary search tree. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
JavaScript
| 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 |
INORDER SUCCESSOR IN BST | PYTHON | LEETCODE 285 • Cracking FAANG • 7,209 views views
Watch 9 more video solutions →Practice Inorder Successor in BST with our built-in code editor and test cases.
Practice on FleetCode