Inorder Successor in a BST

Inorder Successor in a BST asks for the next node in sorted order. It is a clean exercise in using the BST ordering property instead of actually doing a traversal — the whole answer comes from comparisons on the way down.

The slow way first

The obvious idea: do a full inorder traversal of the tree, collect the values in sorted order, find p in that list, and return the next one. That works, but it visits every node — O(n) time and O(n) space for the list — even though the tree already knows its own order.

The question to ask: can I use the BST property to avoid touching the whole tree? In a BST, everything in the left subtree is smaller and everything in the right is larger. That ordering is exactly what "successor" is about, so we should be able to navigate to the answer directly.

The idea: right subtree, or last left turn

There are two cases.

1. p has a right subtree. Then the successor is the smallest value bigger than p — which is the leftmost node of that right subtree. Step into the right child, then go left as far as you can.
2. p has no right subtree. Then the successor must be an ancestor. Walk down from the root toward p. Every time you turn left, that node is bigger than p and is a candidate. The last such left-turn ancestor is the answer. If you never turned left, there is no successor.

The animation walks through case 2, the trickier one: a roving cur pointer descends from the root, and we remember each node where p belongs in its left subtree.

Walk through it

Step through the animation. We want the successor of 14, which has no right child. The pointer cur starts at the root 20: since 14 < 20, we record 20 and turn left. At 8 and at 12, 14 is larger, so we turn right and keep 20 as the candidate. We arrive at 14 itself with nothing to its right, so the walk ends — and the last left turn, 20, is the answer.

Pseudocode

# Case 1: p has a right subtree
if p has a right child:
    node = p.right
    walk left while node.left exists
    return node
 
# Case 2: no right subtree -> look at ancestors
succ = None
cur = root
while cur is not None:
    if p.val < cur.val:
        succ = cur          # turning left: cur is a candidate
        cur = cur.left
    else:
        cur = cur.right     # turning right: candidate unchanged
return succ

The Python solution

def inorder_successor(root, p):
    # Case 1: right subtree exists -> leftmost of it
    if p.right:
        node = p.right
        while node.left:
            node = node.left
        return node
    # Case 2: track the last left-turn ancestor
    succ = None
    cur = root
    while cur:
        if p.val < cur.val:
            succ = cur
            cur = cur.left
        else:
            cur = cur.right
    return succ

• Lines 3-7 handle case 1: if p.right exists, step into it and slide left until there is no left child — that leftmost node is the smallest value bigger than p.
• succ starts as None, so if we never turn left we correctly return None.
• The while cur loop descends the tree comparing p.val to each node.
• Line 12 is the heart of it: when p.val < cur.val, p lives in cur's left subtree, so cur is a better (smaller) candidate than any we had — record it and go left.
• Otherwise p is to the right, so cur is too small to be the successor; go right and keep the old candidate.

Complexity

We follow a single root-to-leaf path, so the work is the tree height h — O(log n) for a balanced BST, O(n) in the worst case for a skewed one. No extra list is needed, so space is O(1).

When this pattern shows up

Practice