LeetCode 510 - Inorder Successor in BST II
This problem asks us to find the in-order successor of a given node inside a Binary Search Tree, abbreviated as BST. Unlike the classic version of the problem, we are not given access to the root of the tree.
Difficulty: 🟡 Medium
Topics: Tree, Binary Search Tree, Binary Tree
Solution
Problem Understanding
This problem asks us to find the in-order successor of a given node inside a Binary Search Tree, abbreviated as BST. Unlike the classic version of the problem, we are not given access to the root of the tree. Instead, we are given only a pointer to a specific node, and each node contains a reference to its parent.
The in-order successor of a node is the next node that would appear during an in-order traversal of the BST. Recall that an in-order traversal visits nodes in this order:
- Left subtree
- Current node
- Right subtree
Because the tree is a BST, an in-order traversal produces values in sorted order. Therefore, the successor of a node is simply the node with the smallest value greater than the current node’s value.
The input consists of a pointer to a single node in the tree. The output should be another Node object representing the successor. If no successor exists, the function should return null in Go or None in Python.
The constraints tell us that the tree can contain up to 10^4 nodes, which is large enough that we should avoid unnecessarily traversing the entire tree if a more targeted solution exists. The problem also guarantees that all node values are unique, which simplifies comparisons and ensures there is only one valid successor.
The important observation is that every node has a parent pointer. This changes the nature of the problem significantly because we can move upward in the tree without needing the root.
Several edge cases are important:
- The given node may be the maximum value in the BST, meaning no successor exists.
- The node may have a right subtree, in which case the successor lies somewhere inside that subtree.
- The node may not have a right subtree, forcing us to move upward through parent pointers.
- The tree may contain only one node.
- The successor may be the direct parent or some higher ancestor.
A naive implementation can easily fail when climbing upward through parent pointers if it does not correctly identify the first ancestor for which the current node lies in the left subtree.
Approaches
Brute Force Approach
The brute force solution reconstructs the traversal order of the BST and then finds the node that appears immediately after the target node.
Since we are not given the root directly, the first step is to climb upward using parent pointers until we reach the root. Once we have the root, we perform a full in-order traversal of the tree and store all visited nodes in a list. After that, we scan through the list to locate the target node and return the next element if it exists.
This approach is correct because an in-order traversal of a BST always produces nodes in sorted order. Therefore, the next node in traversal order is exactly the in-order successor.
However, this method is inefficient because it traverses the entire tree even though the successor can often be found locally near the target node.
Optimal Approach
The optimal solution uses BST properties together with parent pointers.
There are two key cases:
- The node has a right child.
- The node does not have a right child.
If the node has a right subtree, then the successor must be the leftmost node in that right subtree. This works because the successor is the smallest value greater than the current node.
If the node does not have a right subtree, then we move upward through parent pointers until we find an ancestor where the current node lies in the ancestor’s left subtree. That ancestor is the successor.
The important insight is that moving upward skips nodes that are already smaller than or equal to the current node. The first ancestor larger than the current node is exactly the next node in sorted order.
This approach avoids traversing unrelated parts of the tree and works in time proportional to the height of the tree.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n) | O(n) | Performs full in-order traversal and stores all nodes |
| Optimal | O(h) | O(1) | Uses BST structure and parent pointers directly |
Here, n is the number of nodes and h is the height of the tree.
Algorithm Walkthrough
- Check whether the current node has a right child.
If a right subtree exists, the successor must be inside it. Specifically, we move one step right and then continue moving left until no more left child exists. The final node reached is the smallest value greater than the current node. 2. If no right child exists, start moving upward using parent pointers.
In this situation, every node in the current node’s subtree has already been visited during in-order traversal. Therefore, the successor must be an ancestor. 3. Continue climbing upward while the current node is the right child of its parent.
If we are moving upward from a right child, that means the parent and its left subtree have already been visited earlier in traversal order, so they cannot be successors. 4. Stop when either:
- We reach a parent where the current node is the left child.
- We run out of ancestors.
- If such a parent exists, return it.
This parent is the first larger node encountered while moving upward, making it the next node in in-order traversal.
6. If no such parent exists, return None or nil.
This means the original node was the maximum element in the BST and therefore has no successor.
Why it works
The algorithm relies on the ordering guarantees of a BST and the structure of in-order traversal.
If a node has a right subtree, then the next node visited after the current node must be the smallest node inside that right subtree, which is the leftmost descendant.
If a node has no right subtree, then traversal moves upward until it reaches an ancestor that has not yet been visited. The first ancestor for which the current node lies in the left subtree is exactly the next node in traversal order.
Because these are the only two possible traversal transitions in an in-order traversal, the algorithm always returns the correct successor.
Python Solution
"""
# Definition for a Node.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
"""
from typing import Optional
class Solution:
def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':
# Case 1: Node has a right subtree
if node.right:
current = node.right
while current.left:
current = current.left
return current
# Case 2: Move upward until node becomes a left child
current = node
while current.parent and current == current.parent.right:
current = current.parent
return current.parent
The implementation directly mirrors the algorithm described earlier.
The first section checks whether the node has a right child. If it does, the code moves into the right subtree and repeatedly follows left pointers. The leftmost node is returned because it is the smallest node larger than the original node.
The second section handles the case where no right subtree exists. The variable current starts at the target node and climbs upward through parent pointers. While the current node is a right child, we continue moving upward because those ancestors have already been visited in in-order traversal.
Once we find a parent where the current node is the left child, that parent becomes the successor. If we reach the top of the tree without finding such a parent, the node has no successor, so the method returns None.
The implementation uses only constant extra space because it stores only a few pointer variables.
Go Solution
/**
* Definition for Node.
* type Node struct {
* Val int
* Left *Node
* Right *Node
* Parent *Node
* }
*/
func inorderSuccessor(node *Node) *Node {
// Case 1: Right subtree exists
if node.Right != nil {
current := node.Right
for current.Left != nil {
current = current.Left
}
return current
}
// Case 2: Move upward through parents
current := node
for current.Parent != nil && current == current.Parent.Right {
current = current.Parent
}
return current.Parent
}
The Go implementation follows the same logic as the Python version. The main language-specific difference is the use of nil instead of None.
Pointer comparisons are straightforward because nodes are represented as pointers. The loop conditions are also nearly identical to Python. Since Go does not support optional types in the same way as Python, returning nil naturally represents the absence of a successor.
No special handling for integer overflow is required because the algorithm never performs arithmetic operations on node values.
Worked Examples
Example 1
Tree:
2
/ \
1 3
Input: node = 1
The node does not have a right child, so we move upward.
| Step | Current Node | Parent | Action |
|---|---|---|---|
| 1 | 1 | 2 | Node is left child of parent |
| 2 | 1 | 2 | Return parent |
Result: 2
The successor of 1 is 2.
Example 2
Tree:
5
/ \
3 6
/ \
2 4
/
1
Input: node = 6
The node has no right child, so we move upward.
| Step | Current Node | Parent | Action |
|---|---|---|---|
| 1 | 6 | 5 | Current node is right child |
| 2 | 5 | null | Continue upward |
| 3 | 5 | null | No ancestor found |
Result: null
Since 6 is the maximum value in the BST, it has no successor.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(h) | At most one downward traversal and one upward traversal along tree height |
| Space | O(1) | Only a few pointer variables are used |
The algorithm never visits more than the height of the tree. In the worst case, a skewed tree behaves like a linked list, producing O(n) time. In a balanced BST, the height is O(log n).
The space complexity remains constant because the algorithm uses iterative traversal without recursion or auxiliary data structures.
Test Cases
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
class Solution:
def inorderSuccessor(self, node):
if node.right:
current = node.right
while current.left:
current = current.left
return current
current = node
while current.parent and current == current.parent.right:
current = current.parent
return current.parent
def connect(parent, left=None, right=None):
parent.left = left
parent.right = right
if left:
left.parent = parent
if right:
right.parent = parent
sol = Solution()
# Example 1
n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
connect(n2, n1, n3)
assert sol.inorderSuccessor(n1) == n2 # Basic left child successor
# Example 2
n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)
n5 = Node(5)
n6 = Node(6)
connect(n5, n3, n6)
connect(n3, n2, n4)
connect(n2, n1)
assert sol.inorderSuccessor(n6) is None # Maximum node has no successor
# Node with right subtree
assert sol.inorderSuccessor(n3) == n4 # Leftmost node in right subtree
# Successor is ancestor
assert sol.inorderSuccessor(n4) == n5 # Must climb upward
# Single node tree
single = Node(10)
assert sol.inorderSuccessor(single) is None # Single node has no successor
# Deep upward traversal
n10 = Node(10)
n5 = Node(5)
n15 = Node(15)
n12 = Node(12)
connect(n10, n5, n15)
connect(n15, n12)
assert sol.inorderSuccessor(n12) == n15 # Successor found after climbing
# Right child with left descendants
n20 = Node(20)
n10 = Node(10)
n30 = Node(30)
n25 = Node(25)
n22 = Node(22)
connect(n20, n10, n30)
connect(n30, n25)
connect(n25, n22)
assert sol.inorderSuccessor(n20) == n22 # Leftmost node in right subtree
| Test | Why |
|---|---|
[2,1,3], node=1 |
Verifies basic successor case |
node=6 in second example |
Verifies handling of maximum node |
node=3 with right subtree |
Ensures leftmost node search works |
node=4 |
Tests upward traversal to ancestor |
| Single node tree | Validates no-successor edge case |
| Deep upward traversal | Ensures repeated parent climbing works |
| Right subtree with nested left nodes | Confirms correct leftmost descendant selection |
Edge Cases
One important edge case occurs when the target node is the maximum element in the BST. In this situation, there is no larger value in the tree, so the correct answer is None or nil. A buggy implementation might continue traversing upward indefinitely or incorrectly return the root. The algorithm handles this correctly by climbing upward until the parent becomes None.
Another tricky case occurs when the node has a right subtree containing multiple left descendants. The successor is not necessarily the direct right child. Instead, it is the leftmost node inside the right subtree. The implementation explicitly continues moving left until no further left child exists.
A third important edge case occurs when the successor is located among ancestors rather than descendants. For example, if the node has no right child and is deeply nested inside a left subtree, the algorithm must correctly identify the first ancestor for which the node lies in the left branch. The upward traversal loop ensures this by skipping ancestors where the current node is a right child.
A final edge case is a single-node tree. Since the node has neither children nor ancestors, the function should return None. The implementation naturally handles this because both traversal cases immediately terminate without finding a successor.