Validate Binary Search Tree

Hints

1. Build the counter-example before you build the algorithm. Take [10, 5, 15, null, null, 6, 20]. Every parent-child pair is individually correct, yet 6 sits in the right subtree of 10 and is smaller than 10. Any check that looks only at immediate children accepts this tree. Finding this case yourself is most of the problem.
2. Ask what a node needs to know. Not its children's values, but the range its ancestors have already committed it to. Every node inherits an open interval (lo, hi) and is valid exactly when lo < node.val < hi.
3. Work out how the interval narrows. A node with value v and bounds (lo, hi) passes (lo, v) to its left child, because everything on the left must stay below v while still honouring the inherited floor. It passes (v, hi) to the right child. The root starts with (-inf, +inf).
4. Keep the comparison strict. Duplicates are invalid, so the test is lo < node.val < hi, never <=. If the interviewer later allows duplicates on one side, exactly one of the two comparisons relaxes, and you should be able to say which.
5. Consider the in-order alternative. In-order traversal of a valid BST emits values in strictly increasing order. So walk the tree in order, remember only the previous value, and fail the moment the current value is not strictly greater. Same O(n) time, one scalar of state instead of two.
6. Avoid sentinel values drawn from the value range. Node values span the full 32-bit signed range, so initialising bounds with INT_MIN or INT_MAX rejects legitimate trees containing those values. Use unbounded types, nullable bounds, or a wider integer type.

Solution: three approaches

Approach 1 - Bounds recursion: O(n) time, O(h) space

Carry the inherited corridor down the tree. This is the answer most interviewers are listening for.

import math

def is_valid_bst(root):
    def check(node, lo, hi):
        if node is None:
            return True
        if not (lo < node.val < hi):
            return False
        return (check(node.left, lo, node.val) and
                check(node.right, node.val, hi))

    return check(root, -math.inf, math.inf)

Why the bounds narrow the way they do: descending left from a node of value v means every node below must be smaller than v, so v becomes the new ceiling. The floor is untouched, because the constraint from further up the tree still applies. Descending right is the mirror image. Each node therefore carries the conjunction of every constraint its ancestors imposed, compressed into two numbers, because the intersection of nested open intervals is itself an open interval. That compression is what keeps the state constant-sized instead of growing with depth.

Why it is O(n): check is called once per node plus once per null child. A binary tree with n nodes has exactly n + 1 null links, so the total number of calls is 2n + 1, and each does a constant amount of work: two comparisons and two recursive dispatches. Linear in the node count, with no repeated visits because each node is reached through exactly one path from the root.

Why the space is O(h), not O(n): the only memory that grows is the call stack, and its depth equals the current path length from the root, which is bounded by the tree height h. On a balanced tree h = log2(n), so roughly 14 frames for ten thousand nodes. On a degenerate tree that is a single left spine, h = n, and CPython's default limit of 1000 frames turns a correct algorithm into a RecursionError. Approach 3 removes that risk.

Why -inf and +inf rather than INT_MIN and INT_MAX: the constraints allow a node to hold -2^31 exactly. If you seed the recursion with INT_MIN as an exclusive floor, a root holding -2^31 fails lo < node.val and a valid tree is rejected. Python's float infinities dodge this; in Java or C++ use Long bounds or nullable Integer bounds where null means unbounded.

Approach 2 - In-order traversal: O(n) time, O(h) space

A BST's in-order walk is strictly increasing. Validate the tree by validating that sequence.

import math

def is_valid_bst_inorder(root):
    prev = -math.inf

    def inorder(node):
        nonlocal prev
        if node is None:
            return True
        if not inorder(node.left):
            return False
        if node.val <= prev:
            return False
        prev = node.val
        return inorder(node.right)

    return inorder(root)

Why the equivalence holds: in-order visits the entire left subtree, then the node, then the entire right subtree. In a valid BST every value on the left is smaller and every value on the right is larger, so by induction on subtree size the emitted sequence is sorted. Conversely, if the sequence is strictly increasing then no node can be out of position relative to any ancestor, because an ancestor always appears between its left and right subtrees in the traversal order. Checking sortedness of a sequence needs only the previous element, which is why one scalar replaces two bounds.

The practical advantage is that prev generalises. Track a counter alongside it and you have k-th smallest in O(h) space. Track the first and last out-of-order positions and you have the "two nodes were swapped, recover the tree" variant. A common mistake is materialising the full traversal into a list first, which is correct but spends O(n) memory to answer a question that needs O(1) carried state, and gives up the early exit on the first violation. More on iterative walks in iterative BST traversal.

Approach 3 - Iterative with an explicit stack: O(n) time, O(h) space, no recursion limit

The same in-order walk with the call stack made explicit, which is what you write when the tree may be a 10^4-node spine.

import math

def is_valid_bst_iter(root):
    stack, prev, node = [], -math.inf, root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        if node.val <= prev:
            return False
        prev = node.val
        node = node.right
    return True

The inner loop pushes the leftmost spine, then each pop yields the next node in order. The invariant is that the stack always holds the ancestors of the current node whose right subtrees are still unexplored, which is exactly what the runtime's call stack was holding implicitly. Heap-allocated Python lists grow to the available memory rather than to a fixed frame limit, so this version survives inputs that crash the recursive ones. It also keeps the early exit: the first violation returns without touching the rest of the tree.

Complexity comparison

Edge cases to verify

• Single node: [1] is valid. Both children are null and the bounds check passes trivially.
• The grandparent violation: [10, 5, 15, null, null, 6, 20] must return false. If your solution says true, you wrote the local check.
• Equal values: [2, 2] is invalid under strict ordering. A <= in the bounds check accepts it.
• Extreme values: a root of -2^31 or 2^31 - 1 must still validate. This is the case that breaks INT_MIN sentinels.
• Left spine of 10^4 nodes: valid, and deep enough to blow a default recursion limit. Use the iterative walk when the constraint allows this shape.

Where beginners go wrong

• Checking only immediate children. The defining error. left.val < node.val < right.val at every node accepts trees where a deep descendant violates a distant ancestor. The BST property is inherited down the whole path, not asserted one edge at a time.
• Using <= where the definition says <. Duplicates are invalid on both sides. A single relaxed comparison turns a correct solution into one that accepts [2, 2], and no example in the prompt exercises it.
• Seeding bounds with INT_MIN and INT_MAX. Node values reach both limits, so a legitimate root holding -2^31 fails its own floor check. Use infinities, a wider type, or null-means-unbounded.
• Forgetting nonlocal on prev. In Python, assigning to a name inside a nested function creates a new local. Without nonlocal, prev resets to -inf on every call and the check passes for every tree. The function returns true always, which looks like a logic bug and is a scoping one.
• Passing the parent instead of the bounds. Handing a child its parent's value loses every constraint above the parent. It is the local check again, just written with an extra argument so it looks more thorough.
• Materialising the in-order traversal into a list. Correct, but it spends O(n) memory to check a property that needs one carried scalar, and it cannot stop at the first violation. On a tree whose very first two nodes are out of order it still walks all 10^4 nodes.

Interview follow-ups to expect

• "Return the k-th smallest element." In-order traversal visits values in sorted order, so count nodes as you pop and return the k-th. Early-exit as soon as the counter hits k, giving O(h + k) rather than O(n).
• "Exactly two nodes were swapped. Recover the tree." Run the in-order walk and record every position where node.val <= prev. There will be one such dip if the swapped nodes are adjacent in traversal order and two if they are not. Swap the offending values back. O(n) time, O(h) space.
• "Allow duplicates on the right." Relax exactly one comparison: the right child's floor becomes inclusive, so the test is lo <= node.val < hi on right descents. Being able to name which side changes proves you understand the corridor rather than having memorised the code.
• "Validate without recursion." The explicit-stack in-order walk. Worth practising because the same skeleton solves most tree problems once the input can be a 10^4-node spine.
• "How would you validate a B-tree or a red-black tree?" Same idea, more invariants: ordering via bounds, plus structural rules such as equal black-height on every root-to-leaf path. The bounds recursion carries over unchanged and the extra rules ride along in the return value.
• "The tree does not fit in memory." Stream the in-order traversal and keep only prev. The check needs one value of state, so it works on a tree read from disk or over the network in a single pass.

Related reading

• Trees: the module this problem belongs to, covering traversal orders and why in-order is special for search trees.
• Iterative BST Traversal: the explicit-stack pattern, and how to turn any recursive tree walk into a loop.
• Binary Tree Maximum Path Sum: the other side of tree recursion, where the value returned upward differs from the value recorded globally.