BST search

The problem it solves

Binary search needs a sorted array; sorted arrays hate insertion. BST search is binary search transplanted into a structure that can grow: the same one-comparison-halves-the-world discipline, running over linked nodes instead of index arithmetic. Every lookup in every ordered map — every TreeMap.get, every database index probe — is this walk, and its cost is the tree’s height: the structure’s shape is the performance contract.

The searches worth mastering go beyond “is X present?”: floor (largest value ≤ X), ceiling, closest value, k-th smallest with subtree counts — all are the same walk with a memory. Hash maps answer none of these; the ordered-structure questions are precisely where BST search earns its interview slots.

The intuition — and where it breaks down

You’re in a building where every receptionist knows one rule: smaller values are down the left corridor, larger down the right. Ask for 41 at the front desk (the root, holding 50): “smaller — left corridor.” The next desk holds 30: “larger — right.” Each desk consults nobody, remembers nothing about you, and yet the third or fourth desk is standing next to your answer — because each answer discards an entire wing of the building unsearched. The wing behind the “wrong” corridor is not skimmed or sampled; it is provably irrelevant, by the invariant, sight unseen.

Where the analogy breaks, and it’s the same break as the insertion page: corridors aren’t guaranteed short. If the building was constructed by hanging each new office off the last (sorted insertion), the “building” is one infinite hallway and every search walks it end to end. The receptionists’ rule is still perfectly followed — the rule was never the problem; the architecture was. Search inherits whatever shape insertion left behind, and no cleverness at search time can fix a bad shape.

Loading…

A walkthrough you can check

Tree from inserting 50, 30, 70, 20, 40, 60, 80. Search for 40:

1. Desk 50: 40 is smaller → left. The entire right wing — 70, 60, 80 — is eliminated, unvisited.
2. Desk 30: 40 is larger → right. 20 eliminated.
3. Desk 40: found. Three comparisons; three of seven nodes never seen.

Search for 45 in the same tree: same first three hops, but desk 40 says “larger — right corridor,” and the right corridor is empty. That null is not a failure of the search — it’s the proof of absence: every region that could legally contain 45 has been walked or eliminated. The visualization greys out each discarded subtree the moment its parent’s comparison fires, which makes the “cost is depth, not size” claim something you watch rather than accept.

The bonus insight hiding in the miss: the desks you visited — 50, 30, 40 — bracket the missing value. The floor of 45 (which is 40) and its ceiling (50) are always on the search path. That one observation solves closest-value, floor, and ceiling problems with zero extra traversal: walk as if searching, remember the best candidate passed on each side.

The invariant

If the target exists, it lies in the subtree under the cursor. Each comparison shrinks that subtree by discarding one entire child-wing; reaching a null shrinks it to nothing, which converts the invariant into a certificate of absence. Note how exactly this mirrors binary search’s [lo, hi] range — the BST version trades index arithmetic for pointer-following, and the eliminated “half” becomes an eliminated subtree, whose size depends on balance. In a balanced tree each discard is roughly half the remainder; in a chain, each discard is… one node. Same invariant, wildly different value per comparison — the invariant guarantees correctness, never speed.

Complexity, derived

One comparison per level, so O(h) — and the visualization enforces it as a test: comparisons ≤ depth + 1, every run. Balanced, h ≈ log₂ n: a million nodes, twenty desks. Degenerate, h = n. The counters panel makes for a nice experiment: search the same value in the tree built from the random preset versus the sorted preset — same membership, same answer, order-of-magnitude different comparison counts.

Space: O(1) iterative — this walk needs no memory of where it’s been (contrast traversal, which must return). The recursive form spends O(h) stack to express a loop; interviews accept either, production prefers the loop.

Versus the alternatives, since the comparison is always asked: hash maps beat BSTs at exact lookup (O(1) expected) and lose everything ordered — no floor, no range, no sorted iteration. Sorted arrays match balanced-BST search and win on cache behaviour, but pay O(n) per mutation. The BST’s niche is precisely ordered + mutating — say the niche, not just the numbers.

What people get wrong

Recursing into both children. search(left) or search(right) visits everything and forfeits the entire point — it’s the correct algorithm for an unordered tree, which is the tell that someone hasn’t internalized what the invariant buys.

Quoting O(log n) as if it were unconditional. It’s O(h). The interviewer’s next move is a chain-shaped tree; the pre-emptive move is saying “h, which balancing keeps logarithmic” first.

Missing the search-path trick for floor/ceiling/closest. Restarting a second traversal to find the closest value, when the answer was on the path just walked, is the difference between an adequate answer and a good one.

Equality-checking with subtraction. target - node.value overflows at integer extremes in fixed-width languages; three-way comparison or explicit </> branches are the safe idioms.

Implementation notes across languages

The walk is five lines everywhere; the leverage is in knowing each language’s exposed version. Java: TreeMap.floorKey, ceilingKey, higherKey, headMap/tailMap — the search-path tricks, productized; using them in an interview (where allowed) shows you know what the structure is for. C++: std::set::lower_bound is BST search returning the ceiling position; the member function, not the free std::lower_bound, which would degrade to O(n) on set iterators. Python: without a standard tree, the honest translation of “BST search” is bisect over a sorted list (fast search, slow mutation) or sortedcontainers — and explaining that substitution is itself a good answer. JavaScript: hand-rolled or nothing; the iterative walk is the one to write, and while (node) with three branches inside reads cleanest.