Inorder Successor in BST II
Understanding the Problem
We're given a single node in a BST and we need to find the next node that comes after it in an inorder traversal. The constraint that shapes the problem is that we don't have access to the root of the tree. Instead, each node has a parent pointer that lets us walk upward.
In a standard inorder traversal (left, root, right), the successor of a node is the node with the smallest value that is still greater than the given node's value. There are two distinct cases.
If the node has a right subtree, the successor is the leftmost node in that right subtree. If there's no right subtree, the successor is above the node. We walk up using parent pointers until we find an ancestor where our node sits in the left subtree. That ancestor is the successor.
Key Constraints:
1 <= number of nodes <= 10^4→ An O(n) solution runs in time, but the parent pointer enables an O(h) solution that avoids touching most nodes.- All node values are unique → exactly one successor exists, or none if the node holds the maximum value.
- We have a parent pointer but no root access → we can walk up the tree but cannot start a traversal from the root without first reconstructing it.
Approach 1: Find Root + Inorder Traversal
Intuition
If we had access to the root, we could run a standard inorder traversal of the entire tree, collect all nodes in sorted order, and return the node that comes right after the given one.
We don't have the root directly, but parent pointers let us reconstruct it. Walk up from the given node until we reach the node whose parent is null. That node is the root. Once we have it, we run a regular inorder traversal.
This visits every node in the tree even though we only need one specific successor, but it is a correct baseline that the optimal approach will improve on.
Algorithm
- Walk up from the given node using parent pointers until you reach the root (where
parent == null). - Perform a complete inorder traversal of the tree starting from the root, storing nodes in a list.
- Find the given node in the list and return the next node. If the given node is the last in the list, return null.
Visualization and Code
Loading animation...
- Time Complexity: O(n). Walking up to the root takes O(h) time. The inorder traversal visits all n nodes. Scanning the list to find our node takes O(n). Overall: O(n).
- Space Complexity: O(n). We store all n nodes in the inorder list. The recursion stack also uses O(h) space, but the list dominates.
The next approach skips the full traversal. Using the BST structure, we can decide whether the successor lies below the node or above it and go straight there.
Approach 2: Optimal - Two Cases with Parent Pointers
Intuition
An inorder traversal visits the left subtree, then the node, then the right subtree. The successor is the next node visited after the current one. Where that node sits depends on the current node's right subtree, which splits into two cases.
Case 1: The node has a right child. If there's a right subtree, the successor is the leftmost (smallest) node in that right subtree. Why? Because after visiting the current node in inorder, we go into its right subtree, and the first node we visit there is the leftmost one.
Case 2: The node has no right child. With no right subtree, the node and all of its descendants are already visited in inorder order. The successor is the first ancestor where our node sits in the left subtree. We walk up using parent pointers until we find a parent whose left child is the node we came from. That parent is the successor.
If we walk all the way up to the root without finding such an ancestor, then the node has no successor (it's the largest element in the tree).
Case 2 relies on a property of inorder traversal: a parent is visited after its entire left subtree but before its entire right subtree.
If the node is its parent's right child, the parent was already visited before the node, so the parent cannot be the successor. We keep climbing. If the node is its parent's left child, the parent has not been visited yet, and it is the next node in inorder order. That parent is the successor. Reaching a null parent means the node is the last value in the traversal, so there is no successor.
Algorithm
- If the node has a right child, go to the right child, then keep going left until you can't anymore. Return that leftmost node.
- If the node has no right child, walk up using parent pointers. At each step, check if the current node is the left child of its parent. If yes, return the parent. If the current node is the right child, keep walking up.
- If you reach the root (parent is null) without finding a successor, return null.
Visualization and Code
Loading animation...
- Time Complexity: O(h) where h is the height of the tree. In Case 1, we go right once then walk left at most h times. In Case 2, we walk up at most h times. For a balanced BST, h = log n. For a skewed tree, worst case is O(n).
- Space Complexity: O(1). We only use a single pointer variable. No recursion, no extra data structures.