Validate a BST: carry every ancestor constraint

The failure is a forgotten ancestor

A local child comparison accepts the counterexample because 6 is less than 15, while forgetting that the entire right subtree must exceed 10. A correct baseline checks every node against all values in its left and right subtrees. Repeated subtree scans cost O(n²) on a skewed tree. The reusable improvement is to carry the ancestor requirements downward instead of rediscovering them below each node.

Represent a frame as (node, lower, upper) with exclusive bounds; None means an absent bound, not a numeric sentinel. On entry, the bounds summarize every ancestor constraint. Reject ordering when value <= lower or value >= upper. The left child inherits lower and receives current value as upper; the right child receives current value as lower and inherits upper. If all frames pass, each node satisfies every relevant ancestor, which is exactly the strict BST definition. Conversely, a violated ancestor relationship excludes a node from its carried interval, so it is detected.

The logical recursive return is a boolean: this node is in bounds and both child calls return true; an empty child returns true. The reference uses explicit stack frames to avoid Python recursion limits. It records an ordering-failure flag but continues validating shape and value types, so a malformed branch still raises ValueError even when another branch already violates ordering. This distinguishes a validly represented non-BST from an invalid object graph.

Each node is visited once: O(n) time. Trusted-tree DFS needs O(h) frame space, but the reference's identity set detects shared nodes/cycles and raises total auxiliary space to O(n). Integer bounds avoid false failures at extreme values. The function does not prove balance or efficient lookup merely by returning true.

Follow-up 1: allow duplicate keys only in right subtrees

Predict how bounds must carry inclusion as well as value. A left edge adds an exclusive upper bound; a right edge adds an inclusive lower bound.

Globally replacing both comparisons with inclusive ones is wrong: it permits duplicates on the left. This policy also interacts with rotations; a balancing operation may require counts stored within one node instead of duplicate nodes.

Follow-up 2: validate an inorder stream

Inorder traversal emits left, node, right, so strict increase is equivalent to strict BST ordering for a valid tree. A stream of values alone cannot validate the original graph shape; that must be established elsewhere. A senior candidate explains recursive return meaning, bounds, and malformed-versus-false behavior. A lead candidate defines duplicate and structural-validation policy at the serialization boundary rather than silently changing it in one consumer.

Run and check

From the repository root:

cd curriculum/01-code/02-data-structures-algorithms/problems/18-validate-bst
python -m unittest -v test_solution.py

Reference implementation (download file, source below) · Contract and oracle tests (download file, source below). Read the tests after your attempt. A green reference suite verifies the supplied implementation; it does not demonstrate independent transfer. Reimplement one follow-up with the reference closed and explain which old invariant no longer holds.

from dataclasses import dataclass

@dataclass(eq=False)
class Node:
    value: object
    left: "Node | None" = None
    right: "Node | None" = None

def validate_bst(root):
    stack = [(root, None, None)] if root is not None else []
    visited_nodes = set()
    is_bst = True
    while stack:
        node, lower, upper = stack.pop()
        if not isinstance(node, Node) or node in visited_nodes or type(node.value) is not int:
            raise ValueError("expected an integer-valued tree without repeated nodes")
        visited_nodes.add(node)
        value = node.value
        if (lower is not None and value <= lower) or (upper is not None and value >= upper):
            is_bst = False
        if node.right is not None:
            stack.append((node.right, value, upper))
        if node.left is not None:
            stack.append((node.left, lower, value))
    return is_bst

import random
import unittest
from solution import Node, validate_bst

class BSTTests(unittest.TestCase):
    def test_ancestor_bounds_and_empty(self):
        self.assertTrue(validate_bst(None))
        self.assertTrue(validate_bst(Node(2, Node(1), Node(3))))
        self.assertFalse(validate_bst(Node(10, Node(5), Node(15, Node(6), Node(20)))))
        self.assertFalse(validate_bst(Node(2, Node(2))))
        self.assertTrue(validate_bst(Node(0, Node(-(10**100)), Node(10**100))))
        deep = None
        for value in reversed(range(5000)):
            deep = Node(value, right=deep)
        self.assertTrue(validate_bst(deep))

    def test_structural_errors_even_after_order_failure(self):
        shared = Node(2)
        cycle = Node(1)
        cycle.left = cycle
        for root in [Node(True), Node(2, Node(4), 42), Node(1, shared, shared), cycle, 42]:
            with self.assertRaises(ValueError):
                validate_bst(root)

    def test_inorder_oracle(self):
        rng = random.Random(118)
        def build(depth):
            if depth == 0 or rng.random() < .3:
                return None
            return Node(rng.randrange(-10, 11), build(depth - 1), build(depth - 1))
        def inorder(node):
            return [] if node is None else inorder(node.left) + [node.value] + inorder(node.right)
        for _ in range(400):
            root = build(5)
            values = inorder(root)
            expected = all(a < b for a, b in zip(values, values[1:]))
            self.assertEqual(validate_bst(root), expected)

if __name__ == "__main__":
    unittest.main()