BST Validation, in depth: bounds recursion, in-order checks, duplicates and validating real ordered structures

What a valid BST actually requires

A binary search tree stores keys so that search can discard half of the remaining tree at each step. That only works if the ordering holds across whole subtrees, not just between neighbours. The precise invariant: for every node n, every key in the left subtree of n is less than n.key, and every key in the right subtree is greater than n.key.

Two details in that sentence decide most of the bugs. First, it quantifies over every key in the subtree, so a node deep in the tree is constrained by every ancestor where the path turned. Second, it uses strict inequality, which means no duplicates. Many real trees allow duplicates on one side, and the validator must encode the same policy the insert code uses, or it will reject trees the rest of the program considers correct.

An equivalent statement is often easier to code: a binary tree is a valid BST exactly when its in-order traversal (left, node, right) produces a strictly increasing sequence. Each formulation leads to an algorithm.

The local check, and why it fails

The tempting validator compares each node with its children: left child smaller, right child larger, recurse. It runs in linear time and passes every small example people draw. The tree below defeats it.

Node 15 has children 6 and 20, so locally it looks fine. But 6 lives in the right subtree of the root 10, so it must exceed 10. Searching for 6 in this tree starts at 10, goes left because 6 < 10, and never finds it. The tree is corrupt even though no parent-child pair is out of order.

The fix is to carry information down the recursion: each node inherits an interval from its ancestors. Going left tightens the upper bound to the parent's key; going right tightens the lower bound. The labels in the diagram are exactly those intervals.

Algorithm 1: bounds recursion

Pass the open interval (lo, hi) down the tree and check each key against it. Use None for an absent bound instead of a sentinel such as the minimum integer. A sentinel fails when a real key equals it: a tree that legally contains INT_MIN would be rejected by a check of key > INT_MIN. In C++ or Java you can widen to a larger type, or pass pointers or nullable boxes, which also works for keys that are strings or tuples.

class Node:
    __slots__ = ("key", "left", "right")
    def __init__(self, key, left=None, right=None):
        self.key, self.left, self.right = key, left, right

def is_bst(node, lo=None, hi=None):
    """True if every key under node lies strictly inside (lo, hi)."""
    if node is None:
        return True
    if lo is not None and not (lo < node.key):
        return False
    if hi is not None and not (node.key < hi):
        return False
    return is_bst(node.left, lo, node.key) and is_bst(node.right, node.key, hi)

Each node is visited once with constant work, so time is O(n). Space is the recursion depth, O(h), which is O(log n) for a balanced tree and O(n) for a degenerate one. The checks are written as not (lo < key) rather than key <= lo on purpose: if the comparator is broken (a NaN key, for example, where every comparison is false), the node is rejected instead of silently accepted.

Short-circuit evaluation gives an early exit: the right subtree is never visited once the left fails. On large corrupt trees that matters more than the asymptotic bound suggests.

Algorithm 2: in-order traversal with a previous key

The second formulation needs only one piece of state: the last key emitted by the in-order walk. Every new key must be greater than it. An explicit stack makes the walk iterative, which removes the recursion-depth problem entirely and makes the early exit obvious.

def is_bst_inorder(root):
    stack, prev, node = [], None, root
    while stack or node is not None:
        while node is not None:          # descend left, remembering the path
            stack.append(node)
            node = node.left
        node = stack.pop()               # smallest unvisited key
        if prev is not None and not (prev < node.key):
            return False                 # first descent in the sequence
        prev = node.key
        node = node.right
    return True

On the counterexample the walk emits 2, 5, 7, 10, then 6, and stops: 6 is not greater than 10. Time is O(n) worst case, and the stack holds at most h nodes. The in-order version is also the natural one when the tree is exposed only through an iterator: any ordered container that yields keys in order can be validated by checking adjacent pairs, without access to the nodes at all.

If you cannot afford O(h) extra space, Morris traversal threads temporary right pointers through the tree to walk it in O(1) extra space; Morris in-order traversal covers the mechanics. Two cautions for validation: it mutates the tree while running, so it must not run concurrently with readers, and an early return must still restore the threads, so in practice you finish the walk and record the failure instead of returning immediately.

Algorithm 3: bottom-up summaries

The third approach inverts the direction of information flow. Each subtree reports a summary to its parent: whether it is a BST, and the minimum and maximum keys it contains. A node is valid when both children are valid, the left maximum is below its key and the right minimum is above it.

def summarize(node):
    """Return (ok, lo, hi, size) for the subtree rooted at node."""
    if node is None:
        return True, None, None, 0
    lok, llo, lhi, lsz = summarize(node.left)
    rok, rlo, rhi, rsz = summarize(node.right)
    ok = (lok and rok
          and (lhi is None or lhi < node.key)
          and (rlo is None or node.key < rlo))
    lo = llo if llo is not None else node.key
    hi = rhi if rhi is not None else node.key
    return ok, lo, hi, lsz + 1 + rsz

For plain validation this is no better than bounds recursion and it gives up the early exit, because a post-order pass sees children before parents. Its value is that the summary composes. The classic use is finding the largest subtree that is a valid BST: track the best size seen wherever ok is true, in one O(n) pass. The same post-order shape answers the balanced-tree check, and checking a red-black or AVL tree combines both: an ordering summary plus a height or black-height summary from each child.

Duplicates and comparator policy

The textbook invariant forbids equal keys. Production trees rarely do. What matters is that the validator encodes exactly the policy the insert path implements, so write the policy down and test it.

Note the asymmetry. With a duplicates-go-right policy, the in-order sequence 5, 5 is legal, but a tree with a 5 as the left child of another 5 also produces 5, 5 in order while breaking the insert rule, and a search for 5 that stops at the first match may still work while a delete that assumes the policy does not. The in-order check alone cannot distinguish the two shapes; the bounds check with a half-open interval can. Storing a count per node avoids the question altogether and is usually the better design.

The comparator itself must be a strict weak ordering: irreflexive, transitive, and with transitive incomparability. Floating-point keys that may contain NaN violate it. So do comparators that read mutable fields, and string comparisons whose collation changes underneath stored data. A validator is only as good as the comparator it calls, which is why the checks above fail closed.

Recursion depth, cost and when to run validation

Recursive validators are fine on balanced trees: a tree of a billion nodes is about 30 levels deep. They fail on degenerate trees, which are precisely the ones a buggy insert produces. Insert sorted keys into an unbalanced BST and you get a linked list of height n. CPython's default recursion limit is 1,000, so the recursive validator raises RecursionError on a 1,000-node chain, and in C or C++ a deep enough chain overflows the native stack and crashes the process. Use the iterative in-order version, or an explicit stack of (node, lo, hi) tuples for the bounds version, whenever input shape is not under your control.

Validation costs O(n), so it does not belong on the hot path of a container whose operations are O(log n). Run it in tests after every mutation, as a debug-build assertion, or as an offline audit. A common pattern is a randomised property test: generate random insert and delete sequences, apply them to both your tree and a reference sorted list, and after each step assert that the tree validates and its in-order keys equal the reference. That pattern finds rotation bugs in balanced trees far faster than hand-written cases. Order-statistic queries such as k-th smallest make a good second oracle because they depend on the same invariant.

Validating real ordered structures

The same invariant appears on disk. A B-tree index is a wide search tree whose pages must hold keys in order, with each page's keys inside the bounds implied by its parent's separator keys: exactly the bounds-recursion idea, generalised to many children per node. PostgreSQL ships the amcheck extension for this purpose; bt_index_check verifies ordering invariants within B-tree pages without taking heavy locks, and stronger variants check parent-child relationships too.

Real corruption often comes from the comparator rather than from bugs in tree code. A well-known PostgreSQL case was the glibc 2.28 release, which changed collation rules for many locales: text indexes built under the old rules were no longer in order under the new ones, so searches could miss rows that were present. Nothing in the tree changed; the definition of order did. Running an ordering check after an operating system or library upgrade, before trusting the index, is the operational lesson.

Failure modes and trade-offs

• Local-only check. Passes the counterexample above. Always carry bounds or a previous key.
• Sentinel bounds. Using the minimum or maximum integer as an infinite bound rejects valid trees containing those values. Use an explicit absent bound.
• Policy mismatch. Strict validator, permissive insert, or the reverse. Derive both from one written duplicate policy.
• Recursion on hostile input. Degenerate trees exhaust the stack. Prefer iterative versions for untrusted data.
• Mutating traversals. Morris traversal temporarily rewrites pointers; never run it concurrently with readers or abandon it half-way.
• Inconsistent comparators. NaN, mutable keys and collation changes make a correct tree look invalid or an invalid one look valid.

Choosing among the three: bounds recursion is the clearest statement of the invariant and the easiest to adapt to duplicate policies; iterative in-order is the most robust on deep trees and works from an iterator; bottom-up summaries are the right shape when you need more than a yes or no. For a symmetric structural property rather than an ordering one, compare with the symmetric-tree check, which pairs nodes across the tree instead of carrying bounds down it.

What to do next

1. Write your tree's duplicate policy as one sentence, then implement the matching bounds check from the table.
2. Replace any sentinel bounds with absent values, and make comparisons fail closed.
3. Add an iterative validator to the test suite and call it after every mutation in a randomised insert/delete property test against a sorted-list oracle.
4. Extend the validator with a height or colour summary if the tree is self-balancing.
5. For database indexes, schedule an ordering check (for PostgreSQL, amcheck) after operating-system, libc or ICU upgrades.