BST insertion — every question, written out
Build a binary search tree by repeated insertion. The input order decides the shape — sorted input builds a useless chain. The shape decides every later cost.
Read the bst insertion explanation and watch it run
What does one insertion cost, and what is the cost actually made of?
Complexity derivation
O(h) — one comparison per level, down a single path to the first empty slot
Insertion is a search that ends in a null slot, so it walks exactly one root-to-leaf path and does one comparison per node on it. That makes the cost the height, and the height is whatever the arrival order produced. State it as O(h) and then say what controls h — the interviewer’s next question is already the chain-shaped tree.
Follow-up: what does it cost to build a tree from n values that arrive already sorted?
Complexity derivation
O(n²) — the k-th value walks past all k−1 predecessors before finding its slot
Every value is larger than everything already present, so it hangs off the right of the last one and the tree becomes a linked list. The k-th insert then costs k comparisons, and the sum is n(n−1)/2. Prism records 115 steps for eight ascending values against 127 for twelve random ones — half the data, nearly the same work.
See it run — The eighth value has just compared against all seven predecessors to land as another right child.
Follow-up: a self-balancing tree fixes that. What does the fix cost you?
Trade-off & selection
A constant amount of rotation and bookkeeping per mutation, plus per-node balance metadata
AVL trees store a height or balance factor per node and rotate on the way back up; red-black trees store one bit and rebalance more lazily, which is why they win where writes dominate. Either way you are buying a guaranteed logarithmic height with a slightly slower, considerably more intricate mutation. Every mainstream ordered map has made that purchase, because the input that destroys a plain BST — sorted data — is the common case.
What height does a plain BST reach when n values arrive in random order?
Complexity derivation
About 1.39 · log₂ n — genuinely logarithmic, a little worse than perfectly balanced
The proof mirrors quicksort’s average case, with the root playing the part of a random pivot, and it lands on roughly 1.39 · log₂ n. So a plain BST is fine when you can genuinely shuffle the input, and dangerous when you cannot. The practical trouble is that real data arrives sorted more often than randomly — timestamps, ids, imported exports.
Two programs insert the same five values and get different trees. How?
Invariant identification
They inserted in different orders — the first value becomes the root permanently, and every later value is routed by it
The tree is a fossil record of its own insertion order: the first arrival splits the value space forever, and each early value shapes the interrogation of every later one. Insert 5, 3, 8, 1, 4 and you get a bushy tree of height 2; insert the same values sorted and you get a chain of height 4. Same membership, same in-order reading, completely different performance.
See it run — The very first value becomes the root, and nothing will ever move it.
State the BST property precisely. What does the sloppy version get wrong?
Invariant identification
Every value in the left SUBTREE is smaller, not merely the left child
The distinction is where validation questions live: put 6 in the left subtree of 5, hanging off a 3, and every individual link looks fine while the tree is broken. The insertion walk enforces the strong version for free, because each comparison it passes narrows the legal interval for everything below. That is also the correct validation strategy — carry a `(min, max)` bound down the recursion rather than comparing neighbours.
A validator checks `node.left.value < node.value < node.right.value` at every node. Give the tree that fools it.
Code diagnosis
Root 5, left child 3, and 6 as the right child of 3 — every link legal, the tree invalid
Locally, 3 < 5 and 3 < 6 both hold, so the neighbour check is satisfied everywhere — yet 6 sits in the left subtree of 5, which the property forbids. The correct validator passes an open interval down: everything in 5’s left subtree must be below 5, so 6 fails against the inherited upper bound. This is the most-asked follow-up on the whole structure, and the neighbour check is the most-given wrong answer.
Recursive insertion is written `insert(node.left, v)` without assigning the result. What happens?
Code diagnosis
Insertions into empty slots vanish silently, since the new node is never linked to its parent
In the `node.left = insert(node.left, v)` style, the return value IS the link; dropping it means the subtree is rebuilt and thrown away. Values already on the path still get compared, so small tests can pass while a fraction of inserts disappear. The iterative form Prism runs sidesteps the trap entirely by assigning into the parent’s empty slot directly.
What should an insert do when the value is already in the tree?
Edge case reasoning
Any consistent policy works — reject, count in the node, or always go one fixed side
The danger is not the policy, it is the mismatch: insert-left with search-right makes stored values unfindable, and the bug is invisible until a duplicate happens to be queried. Prism’s implementation returns early on equality, so duplicates are simply not stored — the trace deduplicates the input before it starts. Say your policy out loud before you code it, because the interviewer is checking that you noticed there was a decision.
Can an insertion ever displace an existing node or change its parent?
Edge case reasoning
No — the walk stops at the first empty slot, so new values always arrive as leaves
Insertion is purely additive: it follows forced comparisons until a child pointer is null, and writes a new node there. That simplicity is why the operation is so short — and it is also the doom, because a structure that never restructures can never repair a bad shape. The invariant panel says it after every insert, naming the value and the parent it hangs from.
Insert n values into a BST, then read it in order. What sorting algorithm have you built?
Comparison
One that averages O(n log n) and degrades to O(n²) on sorted input — quicksort’s profile, with extra memory
Tree sort and quicksort share an analysis for a reason: the first value inserted plays the same role as a pivot, splitting the rest into smaller and larger. So they have the same average bound, the same quadratic worst case, and the same sensitivity to already-ordered input — except tree sort also allocates a node per element. Knowing that the two are the same argument in different clothes is worth more than either algorithm alone.
When is a plain BST the right choice over a balanced one?
Comparison
When the insertion order is genuinely random or already shuffled, and simplicity is worth more than the guarantee
The honest answer is "rarely, and only when you control the input order" — which is why no standard library ships one. A plain BST is a teaching structure and a reasonable choice inside a program that shuffles before inserting, or where the keys are hashes rather than timestamps. Everywhere else, the sorted-input case arrives eventually and the chain is waiting.
A value walks left from the root, then left again, and finds an empty slot. Where does it end up?
Trace prediction
As the left child of the second node it compared against
The walk stops at the node whose relevant child pointer is null, and the new value hangs from exactly that node on exactly that side. There is no lookahead and no scan — the last comparison made determines both the parent and the slot. The trace states it in words after each insert, naming the value, the side and the parent.
See it run — Two left turns, then the spawn: 4 becomes the left child of 5, not of the root.
Explain BST insertion to someone who does not code, including its flaw. Say it out loud.
Explain it plainly
It is twenty questions, but the questions are chosen by whoever showed up first. The first number through the door plants itself in the middle of the room and becomes the question everyone else gets asked: are you bigger than me or smaller? Smaller, and you are sent to the left; bigger, to the right. Whoever is standing there asks you their own version of the same question, and you keep going until you reach an empty spot — and that is where you stand, forever. You become a question-asker for everyone who arrives after you. Nobody ever moves. That is the whole rule, and it is why looking a number up later is fast: each question throws away everything on the other side. Where it goes wrong is the part people miss. A good twenty-questions player asks questions that split the possibilities in half. This game does not get to choose its questions — the arrivals choose them. So if the numbers walk in already in order, every single one is bigger than everyone present, everyone gets sent right, and you have built a queue rather than a tree. Same numbers, same rules, and now looking something up means asking everybody.
The listener should understand both the mechanism and why the same values can produce a good structure or a useless one. A strong answer volunteers the failure without being prompted, because that is the interesting half.