BST search — every question, written out
Follow one comparison per level; each one discards an entire subtree. Binary search, tree-shaped. Half the tree vanishes per step — while the tree is balanced.
Read the bst search explanation and watch it run
What is the cost of a BST search, stated in a way that is actually true?
Complexity derivation
O(h), where h is the height of the tree — one comparison per level walked
Each comparison rejects the node and one whole subtree, then steps to the other child, so the number of comparisons is bounded by the path length from root to leaf. Saying O(h) first and then saying what controls h is the answer that survives the follow-up; saying O(log n) invites it. The invariants panel names the discarded subtree size at every step, which is where the difference between the two claims becomes visible.
See it run — One comparison at the root, and five nodes are eliminated without being looked at.
Follow-up: what shape makes h equal n, and how does the search behave then?
Complexity derivation
A chain built by sorted insertion — each comparison then discards exactly one node
Insert values in ascending order and every one hangs off the right of the last, so the "tree" is a linked list and the search walks it end to end. Prism’s sorted preset builds exactly this, and its own commentary gives the game away: each comparison reports discarding a subtree of one node. The rule was followed perfectly at every step — the architecture, not the algorithm, is what failed.
See it run — The discard message reads "1 node" — a comparison that bought almost nothing.
Follow-up: can the search itself be changed to cope with a degenerate tree?
Trade-off & selection
No — the shape is fixed by insertion, so the fix belongs in insertion and balancing
Search reads the shape it is given and has no leverage over it, which is why the entire balanced-tree literature — AVL, red-black, B-trees — attaches its work to insertion and deletion. The trade is a rotation or two per mutation in exchange for a height that is provably logarithmic. That is why no mainstream library ships a plain BST: the input that breaks it, sorted data, is the default shape of timestamps and auto-increment ids.
Roughly how many comparisons does a lookup take in a balanced tree of a million nodes?
Complexity derivation
About twenty, since 2²⁰ is just over a million
Height is log₂ n for a balanced tree, and log₂ 1,000,000 is just under 20. The number is worth memorising because it makes the structure’s value concrete: a million records, twenty questions. Random insertion order gives about 1.39 times that, which is still comfortably logarithmic.
What is true at every step of the walk, and what does it let the search skip?
Invariant identification
If the target exists it lies under the cursor, so the discarded subtree provably cannot hold it
This is binary search’s `[lo, hi]` range wearing a different costume: the live region is a subtree instead of an index interval, and one comparison eliminates the rest. The eliminated side is not sampled or skimmed — the ordering property makes it impossible for the target to be there. Note that the invariant guarantees correctness and says nothing at all about speed, because how much a discard is worth depends on the shape.
The walk reaches a null child. What has actually been established?
Edge case reasoning
That the value is absent — every region that could legally contain it has been eliminated
The null is a certificate, not a failure: the search shrank the live subtree at every step, and it has now shrunk to nothing. That is the same logic as binary search ending with `lo > hi`. It also explains why a miss costs the same as a hit — both walk one root-to-leaf path.
The target is absent, but you need the largest value below it. What does the failed search already give you?
Edge case reasoning
The answer is on the path just walked — remember the last node you turned right at
Every node the search passed is either smaller or larger than the target, and the tightest of each kind are the floor and the ceiling. Track two candidates as you walk — update the lower one whenever you go right, the upper one whenever you go left — and both fall out with no extra traversal. This one observation solves floor, ceiling and closest-value in a single pass, and it is exactly what `TreeMap.floorKey` and `std::set::lower_bound` are doing.
A candidate writes `return search(node.left, t) || search(node.right, t)`. It passes every test. What is wrong?
Code diagnosis
It visits every node — correct for an unordered tree, and it discards the BST’s only advantage
Correctness and complexity are separate claims, and this code buys the first by abandoning the second: O(n) instead of O(h), on a structure whose entire purpose is to avoid looking at most of itself. Tests that only assert on the returned value will never notice. The tell an interviewer is listening for is whether the candidate uses the comparison to choose a direction rather than to filter results.
In a fixed-width language, someone branches on the sign of `target - node.value`. Where does it break?
Code diagnosis
At extreme values, where the subtraction overflows and flips the sign of the comparison
A large positive minus a large negative wraps around and comes back negative, so the walk turns the wrong way and reports a present value as missing. Explicit `<` and `>` branches, or a three-way comparison function, never have this problem. It is the same class of bug as the binary-search midpoint, and interviewers who work in Java or C++ do ask about it.
A hash map looks up in O(1) expected time. Why would anyone search a tree instead?
Comparison
Because a tree answers ordered questions — range, floor, ceiling, sorted iteration — that hashing cannot
Hashing destroys order by design, so "what is the next key after this one" has no cheap answer in a hash map. A tree keeps order as structure, which is why database indexes and every `TreeMap` are trees rather than hash tables. Say the niche out loud — ordered plus mutating — rather than reciting the two complexities.
Binary search over a sorted array does the same thing in O(log n). What does the tree buy?
Comparison
Cheap insertion and deletion, where the array must shift O(n) elements per change
The two structures answer lookups equally well, and the sorted array is actually faster per comparison thanks to locality. What it cannot do is change: one insertion means shifting half the elements on average. The tree exists for the mutating case, which is why static lookup tables are still arrays and live indexes are trees.
Why is this search written as a loop rather than as a recursion?
Trade-off & selection
The walk never needs to return anywhere, so the loop costs O(1) space instead of O(h)
Every recursive call here is in tail position — there is no work left to do once the child’s answer comes back — so the frames carry nothing worth keeping. Contrast an in-order traversal, which genuinely must return to a node after finishing its left subtree and therefore genuinely needs the stack. Interviews accept either form; the useful sentence is why one of them is free.
A 14-node tree finds its target at depth 5. How many nodes did the search examine?
Trace prediction
Six — one per level from the root down to the matching node
Comparisons equal depth plus one, because the root is compared at depth 0. The trace makes both numbers visible: the depth pointer ticks up as the cursor descends, and the discarded subtrees grey out beside it. Note that the discarded nodes cost nothing at all — the marking is for you, not for the algorithm.
See it run — The match, with the depth pointer reading 5 and most of the tree greyed out.
Explain how a BST search works to someone who does not code. Say it out loud first.
Explain it plainly
Picture a huge building where every receptionist knows exactly one rule: anything alphabetically before my name is down the left corridor, anything after is down the right. You walk in asking for a name. The receptionist at the front desk does not know where that person sits and does not need to — one glance at your name sends you left or right, and the entire other wing of the building is now ruled out. Not skimmed, not searched quickly: ruled out, because the rule guarantees your name cannot be there. Three or four desks later you are standing at the right office, having ignored almost the whole building. And if you get sent down a corridor that turns out to be empty, that empty corridor is your answer — the person is not in the building, and you have proved it. Where the picture breaks: nobody promised the corridors were short. If the building was extended by tacking each new office onto the end of the last one, it is not a building at all, it is one enormous hallway, and you walk every step of it. The rule is still being followed perfectly. The layout is what let you down, and no cleverness at the front desk can fix it.
The listener should come away understanding that the unvisited part of the structure is ruled out by logic rather than skipped by luck. A strong answer also volunteers the failure mode instead of waiting to be asked.