Find a Dead End in a BST

Find a Dead End in a BST is a deceptively simple tree problem that hides a beautiful idea: as you walk down a binary search tree, every node squeezes the range of values that can still be inserted beneath it. When that range pinches shut, you have found a dead end.

The slow way first

The brute-force reading of the definition is to try, for each leaf, every possible integer and ask "could this value be inserted below the leaf?" That means simulating insertions, which is both slow and awkward to bound. We need a cleaner way to express "no value can go here."

The question to ask: for a given node, exactly which values could still legally be inserted in its subtree? If we knew that allowed window, a dead end is just a leaf whose window has shrunk to nothing.

The idea: carry an allowed range down

Pass a range [lo, hi] down the recursion — the inclusive band of values that could still be inserted at or below the current node. The root starts with [1, INF] (positive integers only).

When you step left into a child, every value there must be less than the current node, so hi tightens to node.val - 1. When you step right, every value must be greater, so lo tightens to node.val + 1. A leaf is a dead end exactly when lo == hi: the window has collapsed to one integer, and the leaf already occupies it.

The key insight: the BST ordering rule itself shrinks the window, so we never simulate an insertion — the bounds do all the work.

Walk through it

Step through the animation. We descend the path 8 → 5 → 2 → 4 → 3. The range starts [1, INF]. Going left to 5 pulls hi to 7; left again to 2 pulls hi to 4; going right to 4 pushes lo to 3; going left to 3 pulls hi to 3. Now the leaf 3 holds [3, 3] — lo == hi, so it is a dead end.

Pseudocode

is_dead_end(node, lo, hi):
    if node is empty:
        return False
    if node is a leaf (no children):
        return lo == hi              # window collapsed -> dead end
    # otherwise tighten the range each way and recurse
    return is_dead_end(node.left,  lo,          node.val - 1)
        or is_dead_end(node.right, node.val + 1, hi)

The Python solution

def is_dead_end(node, lo, hi):
    if node is None:
        return False
    if node.left is None and node.right is None:
        return lo == hi
    return (is_dead_end(node.left, lo, node.val - 1) or
            is_dead_end(node.right, node.val + 1, hi))

• lo and hi are the inclusive bounds on values that could still be inserted at or below node. Call it initially as is_dead_end(root, 1, INF).
• An empty subtree is never a dead end, so it returns False.
• Line 4 detects a leaf — no left and no right child. Line 5 is the whole point: a leaf is a dead end iff lo == hi, meaning the allowed window has pinched down to a single value the leaf already holds.
• Stepping left, hi becomes node.val - 1 (children must be smaller). Stepping right, lo becomes node.val + 1 (children must be larger). The or short-circuits the moment any dead end is found.

Complexity

We touch each of the n nodes once, so time is O(n). The extra space is the recursion stack, O(h) where h is the tree height — O(log n) for a balanced tree, O(n) in the worst case of a skewed tree.

When this pattern shows up

Practice