Given a node in a binary search tree, return the in-order successor of that node in the BST. If that node has no in-order successor, return null.
The successor of a node is the node with the smallest key greater than node.val.
You will have direct access to the node but not to the root of the tree. Each node will have a reference to its parent node. Below is the definition for Node:
class Node {
public int val;
public Node left;
public Node right;
public Node parent;
}
Example 1:
Input: tree = [2,1,3], node = 1 Output: 2 Explanation: 1's in-order successor node is 2. Note that both the node and the return value is of Node type.
Example 2:
Input: tree = [5,3,6,2,4,null,null,1], node = 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 <= 105
Follow up: Could you solve it without looking up any of the node's values?
Problem Overview: Given a node in a Binary Search Tree where each node also stores a parent pointer, return its inorder successor. The successor is the next node visited during an inorder traversal (left → root → right). If no such node exists, return null.
Approach 1: Full Inorder Traversal (O(n) time, O(n) space)
The straightforward solution performs a complete inorder traversal of the binary tree and stores the visited nodes in an array. Once traversal finishes, iterate through the array to locate the given node and return the next element. This works because inorder traversal of a binary search tree produces nodes in sorted order. The downside is unnecessary work: the algorithm visits every node even though the successor might be nearby.
Approach 2: Case Analysis Using Parent Pointers (O(h) time, O(1) space)
The structure provides a parent pointer, which allows upward traversal without needing the root. Two structural cases determine the successor. First, if the node has a right child, the successor is the leftmost node in the right subtree. Move to node.right, then repeatedly follow left pointers until no more exist.
If the node does not have a right child, move upward through parent pointers. Continue climbing while the current node is the right child of its parent. The first time you encounter a node that is the left child of its parent, that parent is the inorder successor. If you reach the top without finding such a relationship, the given node is the largest element and has no successor.
This approach relies on BST ordering properties and avoids scanning unrelated parts of the tree. The traversal depth never exceeds the tree height h, which keeps runtime efficient. Space usage stays constant because only pointer references are used.
Recommended for interviews: The parent-pointer case analysis is the expected solution. It demonstrates understanding of tree traversal properties and BST ordering while keeping complexity at O(h) time and O(1) space. Mentioning the full inorder traversal first shows baseline reasoning, but interviewers typically look for the optimized parent traversal.
If the node has a right subtree, then the in-order successor of node is the leftmost node in the right subtree.
If the node does not have a right subtree, then if node is the right child of its parent, we continue to search upwards until the parent of the node is null, or the node is the left child of its parent. In this case, the parent node is the in-order successor.
The time complexity is O(h), where h is the height of the binary tree. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Full Inorder Traversal | O(n) | O(n) | Simple baseline solution when you want a straightforward traversal without relying on BST properties. |
| Parent Pointer Case Analysis | O(h) | O(1) | Optimal approach when nodes contain parent references; traverses only the relevant subtree or ancestor chain. |
Leetcode 510. Inorder Successor in BST II | Logic Coding • Xian Zhang • 1,091 views views
Watch 8 more video solutions →Practice Inorder Successor in BST II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor