Validate a binary search tree: carry the ancestor bounds

A tree can pass every parent-versus-child check and still put a value in the wrong subtree. The smallest useful test therefore needs a grandchild. This page validates the ordering of an existing tree; the binary tree versus binary search tree guide explains why that ordering matters for search.

The parent check that misses a bug#

Consider this deliberately invalid tree:

       10
      /  \
     5    15
         /  \
        6    20

Locally, everything looks plausible: 5 < 10, 15 > 10, 6 < 15, and 20 > 15. But 6 is in the right subtree of 10. It must therefore be greater than 10, not merely smaller than 15.

The path to 6 supplies two restrictions. Turning right at 10 establishes a lower bound of 10. Turning left at 15 establishes an upper bound of 15. The allowed interval is now strictly between 10 and 15; 6 is outside it. Replacing only 6 with 12 makes the example valid.

This is the strict ordering contract used in the LeetCode validation problem. It is not a claim that every possible BST implementation must reject duplicates.

Try it: carry the ancestor bounds

Use strict ordering, so duplicates are rejected. A parent-only check is not enough.

Choose a case Root 10, left 5, right child of 5 is 7Root 10, right 15, left child of 15 is 6Root 10, left child 10

Carry bounds in an explicit stack#

The following complete Python 3.10+ example stores the pending node together with its permitted bounds. None means that the path has not established a bound. It is not a numeric sentinel, so very large or negative integer keys need no special case.

from __future__ import annotations
from dataclasses import dataclass

@dataclass
class Node:
    value: int
    left: Node | None = None
    right: Node | None = None

def is_valid_bst(root: Node | None) -> bool:
    pending: list[tuple[Node | None, int | None, int | None]] = [
        (root, None, None)
    ]
    while pending:
        node, lower, upper = pending.pop()
        if node is None:
            continue
        if lower is not None and node.value <= lower:
            return False
        if upper is not None and node.value >= upper:
            return False
        pending.append((node.right, node.value, upper))
        pending.append((node.left, lower, node.value))
    return True

invalid = Node(10, Node(5), Node(15, Node(6), Node(20)))
valid = Node(10, Node(5), Node(15, Node(12), Node(20)))
assert not is_valid_bst(invalid)
assert is_valid_bst(valid)
assert is_valid_bst(None)
assert is_valid_bst(Node(0))
assert not is_valid_bst(Node(10, Node(10)))
assert is_valid_bst(Node(0, Node(-(10**100)), Node(10**100)))

When going left, keep the old lower bound and tighten the upper bound to the current value. When going right, tighten the lower bound and keep the old upper bound. Each pending entry therefore carries the restrictions imposed by the entire path, not just the last edge.

The stack performs depth-first traversal. At most n nodes are examined, giving O(n) time for fixed-cost key comparisons. Pending branches require O(h) auxiliary space, where h is tree height, and can require O(n) in the worst case. The explicit stack avoids consuming one Python call frame per level; it does not make a very large tree free to store. For the general traversal order, see tree traversals.

Test the rule, not just the shape#

The two almost-identical example trees test the important boundary: a grandchild can satisfy its parent while violating an ancestor. The duplicate test verifies the strict convention. The zero and large-integer cases guard against treating valid keys as false or choosing an arbitrary minimum and maximum.

An inorder solution offers a useful independent check: collect left subtree, node, then right subtree, and require every value to be strictly larger than the preceding one. Do not use a pre-filled numeric sentinel there either; remember whether a previous value exists.

Both approaches assume the input is a proper, finite tree: no cycles and no node shared by multiple parents. Accepting arbitrary object graphs requires a separate identity/structure check. This implementation intentionally answers the ordering question, not whether untrusted input is structurally a tree. It also assumes integer keys; accepting floats introduces questions such as how to handle NaN.

Next, find the diameter of a binary tree. That problem uses the same shape but ignores key ordering completely—a useful contrast between validating data and measuring a structure.

Questions people also ask

2 QUESTIONS

▸ Are duplicate values allowed in a binary search tree?

That depends on the tree's contract. This validator uses strictly smaller keys on the left and strictly larger keys on the right, so it rejects duplicates. A tree that stores duplicates on one side needs a different, consistently applied bounds rule.

▸ Does an inorder traversal validate a BST?

For a proper binary tree with totally ordered keys and no allowed duplicates, a strictly increasing inorder traversal is equivalent to the BST ordering rule. Comparing only each node with its immediate children is not equivalent.