Inorder Predecessor in a BST

Inorder Predecessor in a BST asks for the node that comes just before a given target in sorted order. It is a clean exercise in using the BST ordering property instead of doing a full traversal — and the answer splits neatly into two cases.

        20
       /  \
      10    30
     /  \     \
    5   15    35
         \
          17

The slow way first

The brute-force approach: do a full inorder traversal, collect every value into a list (which comes out sorted), find the target, and return the element right before it. That works, but it visits every node — O(n) time and O(n) space — and ignores the whole point of a BST.

The question to ask: can the BST ordering let me walk straight to the answer without touching the whole tree? Yes. The predecessor is never far away — it is always reachable by a single downward walk.

The idea: two cases

Split on whether the target has a left subtree.

• Case 1 — target has a left child. Everything in the left subtree is smaller than the target, and the predecessor is the largest of those: go left once, then follow right pointers as far as they go. That rightmost node is the answer.
• Case 2 — no left child. The predecessor must be an ancestor — specifically the lowest ancestor under which the target lies in the right subtree. Searching down from the root for the target, that is exactly the last node where we turned right. Track it in pred and update it every time the search goes right.

Both cases are a single straight-line descent, so the work is bounded by the height of the tree.

Walk through it

Step through the animation. We look for the predecessor of 15, which has no left subtree, so we are in Case 2. Starting at the root, 15 < 20 sends us left without changing pred. At 10, 15 > 10, so we turn right — and record pred = 10. We land on 15 itself; it has no left child, so the search unwinds and the last recorded pred, 10, is the answer. The final steps show Case 1 for the predecessor of 20: go left to 10, then right as far as possible, landing on 17.

Pseudocode

if target has a left child:
    node = target.left
    walk right while node has a right child
    return node                 # max of the left subtree
 
pred = None
cur = root
while cur is not None:
    if target.val > cur.val:    # target is to the right
        pred = cur              # remember this right-turn ancestor
        cur = cur.right
    else:
        cur = cur.left
return pred

The Python solution

def inorder_predecessor(root, target):
    if target.left:
        node = target.left
        while node.right:
            node = node.right
        return node
    pred = None
    cur = root
    while cur:
        if target.val > cur.val:
            pred = cur
            cur = cur.right
        else:
            cur = cur.left
    return pred

• Lines 2-6 handle Case 1: if the target has a left subtree, the predecessor is that subtree maximum — one step left, then right until there is no right child.
• pred is our running answer for Case 2, starting at None (the target might be the smallest value, with no predecessor).
• We search down from the root for the target. target.val > cur.val means the target lives in cur's right subtree, so we just turned right.
• On every right turn we set pred = cur. The last such node is the lowest ancestor with the target on its right — exactly the predecessor.
• When target.val <= cur.val we go left and do not touch pred, because a left turn never produces a smaller-but-closer candidate.

Complexity

For a balanced tree the height h is O(log n), so we find the predecessor in logarithmic time using only a couple of pointers — no list, no recursion stack.

When this pattern shows up

Practice