A binary-search-tree validator compares each node only to its immediate children — what does it wrongly accept?
answer
- the rule constrains subtrees, not neighbours
- a key can pass its parent yet fail an ancestor
- what must every key in a left subtree obey
- carry a range down the recursion
- left call tightens the upper bound
basics
~20 sIt accepts trees that break the ordering globally: a node deep inside a left subtree can exceed the root while still satisfying its own parent. Correct validation carries an inherited (low, high) range down the recursion instead of comparing neighbours.
solid answer
~50 sThe search-tree property is about whole subtrees, not parent-child pairs: every key in a node's left subtree must be smaller than the node, and every key in its right subtree larger — transitively, all the way down. A pairwise check misses violations that only an ancestor can see. Five nodes are enough: root 20, left child 10, right child 30, and under 10 a left child 5 and a right child 25. Every parent-child pair passes (10 < 20, 30 > 20, 5 < 10, 25 > 10), yet 25 sits in the root's left subtree while exceeding 20. The fix is to thread bounds through the recursion: the root starts unbounded, a left call inherits `(low, node.key)` and a right call `(node.key, high)`, and any key outside its inherited range fails. That is O(n) time and O(h) stack. The equivalent alternative is an inorder walk that must produce strictly increasing keys.
code
pseudocode · 8 linesvalid(node):
if node == empty:
return true
if node.left != empty and node.left.key >= node.key:
return false
if node.right != empty and node.right.key <= node.key:
return false
return valid(node.left) and valid(node.right)go deeper
Be ready to state the ordering rule in the strong form — every key in the left subtree, not just the left child — and to draw a small tree where a grandchild breaks it.
Explain the bounds recursion and say exactly which bound each direction tightens, plus the equivalent streaming inorder check and the O(n) time, O(h) space cost of both.
Treat it as a review finding: name the class of bug (a local predicate standing in for a global invariant), produce the counterexample as a regression test, and say why the existing tests missed it.
Own where invariants like this get enforced at all — at every write, behind an assertion in test builds, or in a periodic consistency sweep — and what each choice costs in latency and confidence.
## The invariant is about subtrees, not about pairs A binary search tree is defined by a **global** ordering rule: for every node, *all* keys in its left subtree are smaller than the node's key, and *all* keys in its right subtree are larger. A validator that compares a node with its two direct children checks a strictly weaker property — locally sorted triples — and locally sorted is not the same as globally ordered. ### The counterexample a reviewer should demand ``` 20 / \ 10 30 / \ 5 25 ``` Walk the pairwise check: 10 < 20 passes, 30 > 20 passes, 5 < 10 passes, 25 > 10 passes. The validator returns true. But 25 lives in the root's **left** subtree while being larger than 20, so a search for 25 starting at the root turns left at 20... and by the rule it should have turned right. The structure lies to every lookup, insert and delete that trusts the invariant. Five nodes is the minimum: you need a root, a child to hang the offender under, and the offender itself in a position where only the grandparent can see the violation — plus siblings to make the tree look ordinary in a test fixture. This is why the bug survives review. The buggy predicate is short, reads like the definition, and passes every hand-written test whose violations happen to be shallow. The regression test to add is exactly the five-node shape above. ### The bounds fix Carry the constraint an ancestor imposes down into the recursion: ``` valid(node, low, high): if node == empty: return true if low is present and node.key <= low: return false if high is present and node.key >= high: return false return valid(node.left, low, node.key) and valid(node.right, node.key, high) ``` The root is called with both bounds absent. Descending left tightens the *upper* bound to the current key and leaves the lower one alone; descending right tightens the *lower* bound and leaves the upper one alone. Every node is therefore compared against the nearest ancestor that constrains it from each side, which is precisely the transitive rule. On the counterexample, node 25 is reached with high = 20 and fails immediately. Cost: O(n) time (each node is visited once, constant work per node), O(h) auxiliary space for the recursion stack — O(log n) on a balanced tree, O(n) on a degenerate chain. The check short-circuits: as soon as one node fails, the whole answer is known. ### The inorder alternative An equally correct formulation: an inorder walk of a valid search tree emits keys in strictly increasing order, and any tree whose inorder walk is strictly increasing is a valid search tree. The two statements are equivalent, so this is not a heuristic — it is a second proof-shaped implementation. Do it as a **streaming** check: keep only the previously emitted key and compare, rather than materialising the whole key list, which would cost O(n) extra space for no gain. Bail out at the first non-increasing pair. | Approach | Time | Extra space | Early exit | |---|---|---|---| | Pairwise parent-child check | O(n) | O(h) | yes — but **wrong** | | Inherited (low, high) bounds | O(n) | O(h) | yes | | Streaming inorder, keep previous key | O(n) | O(h) | yes | | Inorder into a list, then scan | O(n) | O(n) | no | ### Misreadings to head off - **Valid is not balanced.** A right-leaning chain 1 -> 2 -> 3 -> 4 is a perfectly valid search tree; it is just a slow one. Validation says nothing about height. - **Recursion does not rescue the local check.** Recursing into both children re-runs the same weak test one level down; a weak test applied everywhere is still weak. Nothing in it ever compares 25 with 20. - **Sorted output is not proof if you only sort it.** Collecting the keys and sorting them proves nothing at all — every tree's key multiset sorts. It is the *inorder* order arriving already increasing that carries the information. - **Equal keys need a stated policy.** Whether keys equal to a node may appear, and on which side, is a separate decision the validator must encode consistently; strict inequalities on both sides mean duplicates are rejected outright.
- Give the smallest tree that the pairwise check accepts but a correct validator rejects.Three nodes suffice for the bug in principle: root 20 with left child 10 whose right child is 25. Every pair passes (10 < 20, 25 > 10) yet 25 exceeds the root while sitting in its left subtree. Adding a right child 30 and a left child 5 makes it a five-node fixture that looks ordinary in a test, which is why the bug survives review.
- How would you write the validation without recursion?Do an iterative inorder walk with an explicit stack: push left spine, pop, compare the popped key with the previously emitted one, fail if it is not strictly greater, then move to the right child. It keeps the O(h) stack explicit rather than relying on call depth, which matters for deep, degenerate trees.
- Why is collecting the inorder keys into a list and checking it is sorted usually the worse implementation?It is correct but wasteful: O(n) extra space to hold keys you compare once, and it cannot bail out at the first violation because the list is built before it is scanned. Keeping a single previous key gives the same answer in O(h) space with an immediate early exit.
saying these in an interview costs you the question
- Compares a node only with its two direct children
- Says recursion makes the local check sufficient
- Confuses valid ordering with balanced height
- Sorts the collected keys and calls that validation
- Materialises the whole inorder list instead of one previous key