A nightly import inserts sorted SKU IDs into a plain binary search tree — what do you flag in review?

seniorshould knowfreq 47%

answer

The code is fine; look at the data
Where did that ordering come from
Every insert descends the same direction
Cost of the build, not just the reads
Sum of 1 through n comparisons

basics

~20 s

Flag that the arrival order is sorted: every key lands to the right of the previous one, so the index becomes a chain of length n. Lookups degrade from O(log n) to O(n), and the import loop itself costs Θ(n²).

solid answer

~50 s

The code is correct — the bug is in the data's arrival order, which is why the diff looks clean. Loading SKU IDs in ascending order means every insert compares greater than everything stored and descends right, producing a one-sided chain. Two costs follow. The import degrades to Θ(n²), because insert number k walks the k-1 nodes already in the chain, so the nightly job creeps from minutes to hours as the catalogue grows. And every later lookup is O(n) instead of O(log n). Nothing fails: the ordering invariant holds, inorder traversal is still sorted, tests pass. In review I would ask where the input order comes from and require one of three fixes — shuffle the batch before inserting, bulk-build a balanced tree by recursive median selection in O(n), or use a self-balancing structure. My standing heuristic: a plain tree fed from any sorted source is a defect.

The code is correct — the bug is in the data's arrival order, which is why the diff looks clean. Loading SKU IDs in ascending order means every insert compares greater than everything stored and descends right, producing a one-sided chain. Two costs follow. The import degrades to Θ(n²), because insert number `k` walks the `k-1` nodes already in the chain, so the nightly job creeps from minutes to hours as the catalogue grows. And every later lookup is O(n) instead of O(log n). Nothing fails: the ordering invariant holds, inorder traversal is still sorted, tests pass. In review I would ask where the input order comes from and require one of three fixes — shuffle the batch before inserting, bulk-build a balanced tree by recursive median selection in O(n), or use a self-balancing structure. My standing heuristic: a plain tree fed from any sorted source is a defect.

code

pseudocode · 13 lines

pseudocode

ids = load_skus()             // returned in ascending id order
root = null
for i in 0..length(ids)-1
    root = bst_insert(root, ids[i])
...
bst_insert(node, key):
    if node == null
        return new_node(key)
    if key < node.key
        node.left = bst_insert(node.left, key)
    else
        node.right = bst_insert(node.right, key)
    return node

go deeper

for a junior

Recognise the trigger: keys arriving in ascending order make every insert go right, so the tree becomes a chain. Know that lookups then cost O(n) even though the results stay correct.

for a middle

Explain both costs — the Θ(n²) build and the O(n) reads — and why unit tests and invariant checks miss the problem entirely. Be able to describe the O(n) balanced bulk-build from a sorted list.

for a senior

Show the reviewer's instinct: ask where the ordering comes from, name the detection signal you would ship with the fix, and choose a remedy that suits who controls future input rather than only patching this batch.

for a principal

Frame it as a class of defect, not one bug: a structure whose complexity depends on caller-supplied ordering will regress the moment a new feed appears. Decide whether the guarantee belongs in the structure or in a pipeline convention.

The shape of the defect

This is the class of bug that survives review because there is nothing wrong with the code. Each line is idiomatic, the insert routine is textbook, the tests pass, and the results are correct. The defect lives in an assumption the code makes silently: that the keys arrive in a well-mixed order. The upstream inventory export sorts by SKU ID, so they do not.

Inserting ascending keys into a plain binary search tree means every new key is greater than every stored key. The search path therefore goes right, right, right, to the end, and the new node is attached there. After n inserts you have a chain of length n — a linked list with two child pointers per node and none of the benefits.

Two costs, and the first one bites first

Most people name the lookup cost and stop. There are two:

The build is Θ(n²). Insert number k walks past the k-1 nodes already in the chain. Summing 1 + 2 + ... + n gives n(n+1)/2 comparisons — quadratic. A catalogue of 10,000 SKUs does about 50 million comparisons and nobody notices; at 200,000 SKUs it is 20 billion, and the nightly job that used to finish in minutes now overruns its window. This is usually the symptom that surfaces first, and it is frequently misdiagnosed as "the import is doing more work because the catalogue grew" — which is true, but the growth is quadratic, not linear.
Every subsequent lookup is O(n). Once built, the index is linear to search. If it backs a request path, the read latency scales with catalogue size.

Why nothing catches it

Correctness is intact. The ordering invariant still holds at every node. An inorder traversal still yields SKUs in sorted order. Range queries still return the right rows.
Unit tests are small. A test inserting five keys is a chain of five, and five is fast. Degeneration is invisible below a few thousand nodes.
The insert code is unchanged. The diff under review may only touch the pipeline that feeds the tree, so the reviewer's eyes are on the wrong file.

This is why the review heuristic has to be about provenance of the order, not about the tree code: whenever a plain binary search tree is fed from a sorted source — a key-ordered query result, a counter-issued ID, a timestamp, an alphabetized file — flag it.

How to confirm it in a running system

Measure height against node count. Instrument the index to report its height and its size. A healthy tree over n nodes has height in the neighbourhood of a small multiple of log2 n; a degenerate one has height close to n. Height divided by log2 n is the single most useful number here, and it is cheap to compute on a schedule.
Count comparisons per lookup. If the average comparisons per read grows linearly with catalogue size across releases, the shape is the cause.
Do not check the invariant. Verifying that inorder is sorted proves nothing — a chain passes that check perfectly.

The fixes, cheapest first

Shuffle the batch before inserting. If the whole load is in memory anyway, a random permutation restores the expected-Θ(log n) shape and the build drops to Θ(n log n). One line, no structural change. The weakness is that it is a convention: the next caller who forgets reintroduces the bug.
Bulk-build from the sorted list. Because the input is already sorted, you can build a perfectly balanced tree directly in O(n): take the median of the range as the root, recurse on the left half for the left subtree and the right half for the right. No comparisons, no shuffling, optimal height. When you already hold sorted data, this strictly dominates inserting it one key at a time — it is faster to build and gives a better tree.
Use a self-balancing tree. AVL or red-black maintains a height bound on every write regardless of arrival order, so no caller has to think about order at all. You pay a little state per node and extra work per write.

What I would say in the review comment

"The insert code is fine, but this feed is sorted by SKU ID, so the tree becomes an n-node chain: the import goes quadratic and lookups go linear. Either bulk-build from the sorted list by recursive median selection — O(n) and perfectly balanced, and we already have the data sorted — or switch the index to a height-balanced tree. Please also emit height and size so we can see this in a dashboard instead of in an incident."

That comment names the mechanism, the two costs, a concrete fix that exploits the sortedness rather than fighting it, and a detection signal — which is what separates a senior review from "this might be slow".

## The shape of the defect This is the class of bug that survives review because there is nothing wrong with the code. Each line is idiomatic, the insert routine is textbook, the tests pass, and the results are correct. The defect lives in an *assumption* the code makes silently: that the keys arrive in a well-mixed order. The upstream inventory export sorts by SKU ID, so they do not. Inserting ascending keys into a plain binary search tree means every new key is greater than every stored key. The search path therefore goes right, right, right, to the end, and the new node is attached there. After `n` inserts you have a chain of length `n` — a linked list with two child pointers per node and none of the benefits. ## Two costs, and the first one bites first Most people name the lookup cost and stop. There are two: 1. **The build is Θ(n²).** Insert number `k` walks past the `k-1` nodes already in the chain. Summing `1 + 2 + ... + n` gives `n(n+1)/2` comparisons — quadratic. A catalogue of 10,000 SKUs does about 50 million comparisons and nobody notices; at 200,000 SKUs it is 20 billion, and the nightly job that used to finish in minutes now overruns its window. This is usually the symptom that surfaces first, and it is frequently misdiagnosed as "the import is doing more work because the catalogue grew" — which is true, but the growth is quadratic, not linear. 2. **Every subsequent lookup is O(n).** Once built, the index is linear to search. If it backs a request path, the read latency scales with catalogue size. ## Why nothing catches it - **Correctness is intact.** The ordering invariant still holds at every node. An inorder traversal still yields SKUs in sorted order. Range queries still return the right rows. - **Unit tests are small.** A test inserting five keys is a chain of five, and five is fast. Degeneration is invisible below a few thousand nodes. - **The insert code is unchanged.** The diff under review may only touch the pipeline that feeds the tree, so the reviewer's eyes are on the wrong file. This is why the review heuristic has to be about **provenance of the order**, not about the tree code: whenever a plain binary search tree is fed from a sorted source — a key-ordered query result, a counter-issued ID, a timestamp, an alphabetized file — flag it. ## How to confirm it in a running system - **Measure height against node count.** Instrument the index to report its height and its size. A healthy tree over `n` nodes has height in the neighbourhood of a small multiple of `log2 n`; a degenerate one has height close to `n`. Height divided by `log2 n` is the single most useful number here, and it is cheap to compute on a schedule. - **Count comparisons per lookup.** If the average comparisons per read grows linearly with catalogue size across releases, the shape is the cause. - **Do not check the invariant.** Verifying that inorder is sorted proves nothing — a chain passes that check perfectly. ## The fixes, cheapest first 1. **Shuffle the batch before inserting.** If the whole load is in memory anyway, a random permutation restores the expected-Θ(log n) shape and the build drops to Θ(n log n). One line, no structural change. The weakness is that it is a convention: the next caller who forgets reintroduces the bug. 2. **Bulk-build from the sorted list.** Because the input is already sorted, you can build a *perfectly* balanced tree directly in O(n): take the median of the range as the root, recurse on the left half for the left subtree and the right half for the right. No comparisons, no shuffling, optimal height. When you already hold sorted data, this strictly dominates inserting it one key at a time — it is faster to build and gives a better tree. 3. **Use a self-balancing tree.** AVL or red-black maintains a height bound on every write regardless of arrival order, so no caller has to think about order at all. You pay a little state per node and extra work per write. ## What I would say in the review comment "The insert code is fine, but this feed is sorted by SKU ID, so the tree becomes an `n`-node chain: the import goes quadratic and lookups go linear. Either bulk-build from the sorted list by recursive median selection — O(n) and perfectly balanced, and we already have the data sorted — or switch the index to a height-balanced tree. Please also emit height and size so we can see this in a dashboard instead of in an incident." That comment names the mechanism, the two costs, a concrete fix that exploits the sortedness rather than fighting it, and a detection signal — which is what separates a senior review from "this might be slow".

Why does the import itself, not just later lookups, become the first visible symptom?
Each insert walks the chain built so far, so the k-th insert costs about k comparisons and the whole load costs n(n+1)/2 — quadratic in catalogue size. Doubling the SKU count quadruples the job's runtime, so a nightly window that was comfortable stops being comfortable well before read latency draws attention. Reads only degrade for keys actually requested; the build pays the full cost every night.
The input is already sorted. Can you exploit that rather than shuffling it away?
Yes, and it is the better fix. From a sorted list you can build a perfectly balanced tree in O(n): make the middle element the root, recurse on the left half and the right half. No comparisons are needed because the ordering is already known. It is faster than inserting one key at a time and produces a better tree than shuffling would.
How would you tell a healthy index from a degenerate one in production monitoring?
Export the tree's height alongside its node count and watch the ratio of height to log2(size). A bushy tree keeps that ratio to a small constant; a chain drives it toward size/log2(size) and climbing. Do not rely on invariant checks — a degenerate tree still traverses in sorted order and passes every correctness assertion you can write.

saying these in an interview costs you the question

Reviews only the insert code, not the data's order
Names the lookup cost but misses the quadratic build
Suggests verifying inorder order as the check
Assumes correct results mean correct complexity
Sorts the input again to fix it

A nightly import inserts sorted SKU IDs into a plain binary search tree — what do you flag in review?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The shape of the defect

Two costs, and the first one bites first

Why nothing catches it

How to confirm it in a running system

The fixes, cheapest first

What I would say in the review comment

▾common follow-ups3 questions

▾red flags5 flags

§ context

▾related questions7 questions

▾related topics4 topics

The shape of the defect

Two costs, and the first one bites first

Why nothing catches it

How to confirm it in a running system

The fixes, cheapest first

What I would say in the review comment

answer

go deeper

context