Problem 26 · Trees

Validate Binary Search Tree

MediumClassic DSA & systems

01Problem

Determine whether a binary tree is a valid BST: every node's left subtree holds strictly smaller keys and its right subtree strictly larger keys.

02Key insight

Checking only parent-child pairs is the classic bug; propagate an open (low, high) bound down the tree, or verify that an in-order traversal is strictly increasing.

03Solution

solution.pypython22 lines

from __future__ import annotations
from dataclasses import dataclass
from typing import Optional

@dataclass
class TreeNode:
    val: int
    left: Optional[TreeNode] = None
    right: Optional[TreeNode] = None

def is_valid_bst(root: Optional[TreeNode]) -> bool:
    # Iterative to avoid recursion limits on skewed trees.
    stack: list[tuple[Optional[TreeNode], float, float]] = [(root, float("-inf"), float("inf"))]
    while stack:
        node, low, high = stack.pop()
        if not node:
            continue
        if not low < node.val < high:
            return False
        stack.append((node.left, low, node.val))
        stack.append((node.right, node.val, high))
    return True

Try it first.

TimeO(n)

SpaceO(h)

tests.py · 4 passing

tests.pypython5 lines

T = TreeNode
assert is_valid_bst(T(2, T(1), T(3)))
assert not is_valid_bst(T(5, T(1), T(4, T(3), T(6))))
assert not is_valid_bst(T(5, T(4), T(6, T(3), T(7))))  # 3 violates root bound
assert is_valid_bst(None) and not is_valid_bst(T(1, T(1)))

04Staff-level follow-up

Keys are arbitrary comparables, not numbers? Use None as the unbounded sentinel instead of infinities so the check works for strings or tuples.