What does the binary search tree ordering invariant require beyond parent-child comparisons?
answer
- Think about what a lookup discards
- The rule spans subtrees, not pairs
- A grandchild can betray a tidy parent
- Root 10, left child 5, right grandchild 12
- Violation means wrong answer, not slow answer
basics
~20 sThe binary search tree invariant is subtree-wide: every key in a node's whole left subtree is smaller than that node, and every key in its right subtree is larger. Comparing a node against only its children is not enough.
solid answer
~50 sThe invariant is stated over whole subtrees and must hold at every node, not just the root: for any node `k`, all keys in `k`'s left subtree are less than `k`, all keys in its right subtree are greater, and the same holds recursively inside each subtree. The classic wrong answer is "each node is bigger than its left child and smaller than its right child" — that is only a local check. Take root `10`, left child `5`, and give `5` a right child `12`. Every parent-child pair is locally fine, but `12` sits in the root's left subtree while exceeding `10`. A lookup for `12` compares against `10`, steps right, finds nothing, and reports the key absent even though it is stored. That is the point: the invariant licenses discarding an entire subtree at each step, so breaking it makes reads silently wrong, not slow.
go deeper
Be ready to state the invariant in one sentence and to stress that it covers entire subtrees, not just a node and its two children. Expect to be handed a four-node tree and asked whether it is valid.
Expect to explain the mechanism: why a single misplaced grandchild makes a lookup report 'absent' for a key that is stored, and why the standard insert-at-the-failed-search-slot rule preserves the invariant automatically.
Demonstrate that a violated invariant is a correctness fault, not a slowdown — reads go quiet and wrong. Say where such violations get introduced in real code (hand-rolled insert or delete) and what test catches them.
Own the convention for equal keys: strict ordering with duplicates forbidden, a documented side for equal keys, or counts stored on the node. Every operation in the codebase must agree on that choice or stored records become unreachable.
## The statement that actually matters A binary search tree is a binary tree whose nodes carry ordered keys and obey one rule. For **every** node `k`: - every key stored anywhere in `k`'s left subtree is less than `k`'s key, and - every key stored anywhere in `k`'s right subtree is greater than `k`'s key. The words doing the work are *anywhere* and *every node*. The rule is quantified over whole subtrees, and it is required recursively — a tree is a binary search tree only if each of its subtrees is one too. Nothing in the rule mentions siblings, depth, or balance; two subtrees may be wildly different sizes and the tree is still perfectly valid. ## The local-versus-global trap The misconception an interviewer is fishing for is the *parent-child* version: "a node is bigger than its left child and smaller than its right child." That is a strictly weaker condition, and the gap between the two is easy to exhibit: ``` 10 / \ 5 15 \ 12 ``` Check the pairs: `5 < 10`, `15 > 10`, `12 > 5`. Every parent-child relationship is ordered correctly, so the weak rule is satisfied. But `12` lives in the root's left subtree while `12 > 10`, so the real invariant is violated at the root. The damage shows up in a lookup. Searching for `12` starts at `10`, sees `12 > 10`, and steps **right** into the subtree rooted at `15`. It sees `12 < 15`, steps left, finds an empty slot, and answers "not present" — for a key that is sitting in the tree. Nothing crashes. No assertion fires. The structure still looks like a tidy little tree in a debugger. This is why the invariant is worth stating precisely: it is not decoration, it is the precondition that makes the search algorithm correct. ## Why search is allowed to throw away half the tree A lookup for `x` at node `k` does one comparison and then commits: if `x < k`, it descends left and never looks at the right subtree again; if `x > k`, it descends right. That commitment is only sound because the invariant promises that *no* key greater than `k` hides on the left and *no* key smaller than `k` hides on the right. Weaken the promise to parent-child pairs and the commitment becomes a guess. The search still runs, still terminates, and still costs one comparison per level — it just returns the wrong answer some of the time. So the correct mental model is: the invariant buys **correctness of pruning**. Height buys speed. They are separate properties, and confusing them is a common stumble — a valid binary search tree can be slow (a long thin one), and a fast-looking, nicely bushy tree can be invalid. ## Insertion preserves it for free The standard insertion is: run the search for the new key; when the descent reaches a missing child slot, attach the new node there. This preserves the invariant automatically, and the reason is worth being able to say out loud. The path from the root to that empty slot is exactly the list of constraints the new key satisfies — at each node on the path the key compared smaller or larger, which is precisely the condition for it to belong in that subtree. Attaching anywhere else, for instance "at the shallowest free slot" to keep the tree bushy, is how a hand-written insert produces the invalid tree above. ## Two immediate consequences **Inorder order.** Walking left subtree, then node, then right subtree emits the keys in ascending order. This falls straight out of the invariant: everything the left subtree emits is smaller than the node, everything the right subtree emits is larger, and by recursion each subtree emits its own keys sorted. If an inorder walk of your structure ever produces a value out of order, the invariant is broken somewhere. **Equal keys need a decision.** The rule as stated uses strict less-than and greater-than, which leaves equal keys homeless. Implementations pick one convention and enforce it everywhere: forbid duplicates outright, always send equal keys to one designated side, or store a count or a bucket of records on the node. Any of these is defensible; mixing two of them within one codebase is not, because insert and lookup will then disagree about where an equal key lives and a stored record becomes unreachable. ## What a strong answer sounds like State the subtree-wide rule in one sentence, note that it must hold at every node, offer the three-node counterexample that passes the local check, and finish with the consequence: a violation is a silent wrong answer from a read, not a performance problem.
- Does the invariant say anything about the two subtrees of a node relative to each other?Yes, transitively: every key on the left is below the node's key and every key on the right is above it, so the whole left subtree is below the whole right subtree. What it says nothing about is their sizes or heights — one may hold a thousand keys and the other none, and the tree is still valid.
- Why does the standard insertion never break the invariant?Because it inserts exactly where the search for that key fails. The root-to-slot path is the set of comparisons the new key already satisfies, so placing it there keeps every ancestor's subtree rule true. Any placement chosen for shape rather than by comparison can violate it.
- What order does an inorder walk emit, and why does that follow from the invariant?Ascending key order. Left subtree first emits everything smaller than the node, then the node, then the right subtree emits everything larger — and each subtree does the same internally by recursion. It is the cheapest sanity check you have: an out-of-order pair proves the invariant is broken.
Sorting a filing cabinet drawer by drawer is not enough; the rule has to hold for every folder inside every drawer, or a document filed correctly relative to its neighbour still ends up in the wrong drawer.
saying these in an interview costs you the question
- States the rule only for a node and its two children
- Thinks a broken invariant makes lookups slower, not wrong
- Believes the rule only has to hold at the root
- Says every binary tree can be searched by comparison
- Confuses the ordering rule with a balance requirement