Problem Description

You are given a node in a binary search tree (BST) and need to find its in-order successor. The in-order successor is the node with the smallest value that is greater than the given node's value. If no such node exists, return null.

Each node in the tree has the following structure:

• val: the integer value stored in the node
• left: reference to the left child
• right: reference to the right child
• parent: reference to the parent node

The key constraint is that you have direct access only to the given node, not the root of the tree. You must use the parent pointers to navigate the tree when necessary.

In a BST's in-order traversal (left → root → right), the successor of a node is simply the next node that would be visited after it. For example, if the in-order traversal of a BST produces the sequence [2, 3, 4, 6, 7, 9] and you're given the node with value 4, its in-order successor would be the node with value 6.

The solution requires handling two main cases:

1. If the node has a right subtree: The successor is the leftmost node in that right subtree (the minimum value in the right subtree).

2. If the node has no right subtree: You need to traverse upward using parent pointers. Keep moving up while the current node is a right child of its parent. The successor is the first ancestor where the node appears in the left subtree, or null if you reach the root without finding such an ancestor.

Intuition

To understand how to find the in-order successor, let's first recall what in-order traversal means in a BST: we visit nodes in ascending order of their values (left → root → right).

When we're at a particular node and want to find the next node in this sequence, we need to think about where we would go next if we were performing an in-order traversal.

Consider two scenarios:

Scenario 1: The node has a right child If we're at a node during in-order traversal and it has a right subtree, the next step would be to explore that right subtree. But we don't visit the right child immediately - we need to find the smallest value in that right subtree (since in-order means ascending order). The smallest value in any BST subtree is always the leftmost node. So we go right once, then keep going left as far as possible.

For example, if we're at node 5 and it has a right child 8, and 8 has a left child 6, and 6 has a left child 7, then the successor of 5 is 6 (the leftmost node in the right subtree).

Scenario 2: The node has no right child This is trickier. If there's no right subtree, the successor must be somewhere above us (an ancestor). But which ancestor?

Think about it this way: if we're a left child of our parent, then our parent hasn't been visited yet in the in-order traversal (because in-order visits left child first, then parent). So our parent would be our successor.

But if we're a right child of our parent, that means our parent was already visited before us (parent comes before right child in in-order). So we need to keep going up until we find an ancestor where we came from the left subtree. That ancestor would be the first unvisited ancestor, making it our successor.

The pattern is: keep going up while we're a right child, because all those ancestors have already been visited. Stop when we're a left child (or reach null), and that parent is our successor.

Learn more about Tree, Binary Search Tree and Binary Tree patterns.

Solution Approach

The implementation follows the two cases we identified in our intuition:

Case 1: Node has a right subtree

if node.right:
    node = node.right
    while node.left:
        node = node.left
    return node

When the node has a right child, we first move to the right child, then keep traversing left as far as possible. This finds the minimum value in the right subtree, which is the in-order successor. The while loop continues until we reach a node with no left child - that's our leftmost node.

Case 2: Node has no right subtree

while node.parent and node.parent.right is node:
    node = node.parent
return node.parent

When there's no right child, we need to traverse upward using parent pointers. The key insight is that we keep going up as long as we're the right child of our parent (node.parent.right is node). This is because if we're a right child, our parent was already visited before us in the in-order traversal.

The loop terminates in one of two situations:

1. We find a parent where we're the left child - this parent is our successor (returned by node.parent)
2. We reach the root (where node.parent becomes None) - this means the original node was the rightmost node in the entire tree, so it has no successor (returns None)

The algorithm efficiently uses the parent pointers to navigate the tree without needing access to the root. The time complexity is O(h) where h is the height of the tree, as in the worst case we might traverse from a leaf to the root. The space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through finding the in-order successor for different nodes in this BST:

        20
       /  \
      8    22
     / \
    4   12
       /  \
      10   14

Example 1: Finding successor of node 8 (has right subtree)

Starting at node 8, we check if it has a right child. It does - node 12.

Following Case 1, we:

1. Move to the right child: node = 12
2. Keep going left while possible: node = 10 (since 12 has a left child)
3. Check if 10 has a left child - it doesn't, so we stop

The successor of 8 is 10.

Example 2: Finding successor of node 14 (no right subtree)

Starting at node 14, we check if it has a right child. It doesn't.

Following Case 2, we traverse upward:

1. Check parent: node.parent = 12. Are we the right child? Yes (12.right = 14)
2. Move up: node = 12
3. Check parent: node.parent = 8. Are we the right child? Yes (8.right = 12)
4. Move up: node = 8
5. Check parent: node.parent = 20. Are we the right child? No (20.left = 8)
6. Stop! We're a left child, so our parent 20 is the successor

The successor of 14 is 20.

Example 3: Finding successor of node 22 (rightmost node)

Starting at node 22, we check if it has a right child. It doesn't.

Following Case 2:

1. Check parent: node.parent = 20. Are we the right child? Yes (20.right = 22)
2. Move up: node = 20
3. Check parent: node.parent = None (20 is the root)
4. Stop! We've reached the root

Since node.parent is None, we return None. Node 22 has no successor as it's the rightmost node in the tree.

Solution Implementation

Time and Space Complexity

Time Complexity: O(h), where h is the height of the binary tree.

The algorithm finds the inorder successor of a given node in a binary search tree with parent pointers. There are two cases:

1. If the node has a right subtree, the successor is the leftmost node in that right subtree. In the worst case, we traverse from the node's right child all the way down to the leftmost leaf, which takes O(h) time.

2. If the node has no right subtree, we need to traverse up the tree using parent pointers until we find a node that is the left child of its parent (or reach null). In the worst case, we traverse from a leaf node all the way up to the root, which also takes O(h) time.

Since we only traverse either down or up the tree (never both completely), and the maximum distance we can travel is the height of the tree, the time complexity is O(h).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space. We only maintain a single pointer reference (node) that gets reassigned during the traversal. No additional data structures like stacks, queues, or recursive call stacks are used. The space used does not depend on the size or height of the tree, making it constant space O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Using Value Comparison Instead of Reference Comparison

The Problem: A common mistake is using value comparison (node.parent.right == node) instead of reference/identity comparison (node.parent.right is node) when traversing upward.

# WRONG - This compares values, not references
while node.parent and node.parent.right == node:
    node = node.parent

Why It's Wrong: In a BST, duplicate values might exist in different nodes. Using == compares the values of nodes, which could lead to incorrect results if two different nodes have the same value. The is operator checks if two variables refer to the exact same object in memory.

The Fix: Always use is for reference comparison:

# CORRECT - This checks if it's the same node object
while node.parent and node.parent.right is node:
    node = node.parent

Pitfall 2: Forgetting to Handle the Root Node Case

The Problem: Not properly handling when the given node is already the rightmost node in the entire tree (has no successor).

# WRONG - Might cause AttributeError
def inorderSuccessor(self, node):
    if node.right:
        # ... find leftmost in right subtree
  
    while node.parent.right is node:  # Missing null check!
        node = node.parent
    return node.parent

Why It's Wrong: If the node is the rightmost node in the tree, we'll eventually reach the root where node.parent becomes None. Trying to access None.right will raise an AttributeError.

The Fix: Always check if node.parent exists before accessing its attributes:

# CORRECT - Checks for None before accessing
while node.parent and node.parent.right is node:
    node = node.parent
return node.parent  # Returns None if we've reached root

Pitfall 3: Modifying the Original Node Reference Unnecessarily in Case 1

The Problem: Reusing the same variable name can be confusing and might lead to bugs if you need the original reference later:

# Potentially confusing
if node.right:
    node = node.right  # Lost original reference
    while node.left:
        node = node.left
    return node

The Fix: Use a different variable name for clarity:

# CLEARER - Preserves original reference
if node.right:
    current = node.right
    while current.left:
        current = current.left
    return current

This makes the code more maintainable and easier to debug, especially if you need to add logging or additional logic that references the original node.