A bounds-based search-tree validator rejects a valid tree holding the most negative key — why?

## The bug is in the seed, not in the recursion The bounds formulation of search-tree validation is correct: each node is checked against a range inherited from its ancestors, the left call tightens the ceiling and the right call raises the floor. The root, however, is unconstrained, and that unconstrained state has to be represented somehow. Reaching for the key type's minimum and maximum representable values is the natural move and the source of a whole family of false rejections. ### Why no choice of comparison saves it Suppose keys are signed integers and the recursion starts with low = the most negative representable value, high = the largest. The body rejects when `key <= low` or `key >= high`. - A single-node tree whose key is the most negative representable value is **valid**, but `key <= low` is true, so it is rejected. Same at the top of the range. - Loosen the test to `key < low` and the sentinel case passes — but now the *genuine* bounds passed down the recursion are compared non-strictly, so a descendant whose key exactly equals a constraining ancestor is accepted. That is a false acceptance, and a worse bug than the one you removed, because it fires on ordinary data rather than at the extremes. The conflict is structural: the sentinel wants a permissive comparison and the real bounds want a strict one, and a single operator cannot be both. Any fix has to distinguish "no constraint" from "a constraint that happens to be extreme". ### Fixes, best first 1. **Optional bounds.** Model each side as present-or-absent and skip the comparison entirely when absent. The root passes both as absent; every tightened bound is by construction a real key. This is exact for every key type, including ones with no natural sentinel at all such as strings or composite keys, and it is the version to reach for by default. 2. **Widen the bound type.** Carry bounds in a type whose range strictly contains the key type's, so sentinels lie outside anything a key can be. This works, and it is a common quick fix, but it is fragile: it silently stops working the day the key type is widened to match, and it does not generalise to non-numeric keys. 3. **Pass ancestor references instead of values.** Hand down the nearest constraining ancestor node on each side, treating an absent ancestor as unconstrained. Mechanically identical to optional bounds, and it reads well when the comparison is a custom ordering rather than `<`. 4. **Streaming inorder with a first-visit flag.** The inorder formulation — keys must arrive strictly increasing — has exactly the same trap if you seed the previous key with an extreme value: a first key equal to that sentinel is wrongly rejected. Track "have we emitted anything yet" as a separate flag and skip the comparison on the first key. ### The other half of the boundary question: equal keys A validator cannot be written until someone answers what equal keys mean in this structure, and the answer must match what insert, search and delete do: - **Duplicates rejected.** Both comparisons are strict, and validation fails on any repeated key. Simple, and usually right when keys identify records. - **Duplicates allowed on one designated side.** Pick a side once and apply it everywhere — say equal keys always go right. Then the right-hand comparison becomes non-strict while the left stays strict, and every other operation must follow the same convention or lookups will miss records that are physically present. - **Duplicates collapsed into a count on the node.** The tree stays strictly ordered and multiplicity lives in the payload. Validation is strict on both sides, and range queries stay simple. The failure mode when the policy is unwritten is that different code paths disagree: one path inserts equal keys left, another searches right, and records become unreachable without any structural corruption a validator would catch. Writing the policy into the validator makes it executable documentation. ### Testing this properly Example-based tests will not find the sentinel bug because nobody writes a fixture with an extreme key by hand. Two habits do find it: include the extreme representable values of the key domain in a boundary-value test set, and property-test the invariant — build a tree by inserting a random permutation of keys, assert it validates, then perturb one node's key and assert it does not. Both are cheap, and both catch the class rather than the instance.