Validate Binary Search Tree

Collect in-order values

An in-order traversal visits a node's left subtree, then the node, then its right subtree. For a valid BST, that visit order must produce a strictly increasing sequence. Collect the sequence, then compare every neighboring pair.

def is_valid_bst(root: TreeNode | None) -> bool:
    values: list[int] = []
    stack: list[TreeNode] = []
    current = root
 
    while current is not None or stack:
        while current is not None:
            stack.append(current)
            current = current.left
        current = stack.pop()
        values.append(current.val)
        current = current.right
 
    return all(values[i - 1] < values[i] for i in range(1, len(values)))

The strict < matters. Using <= would quietly accept duplicate values.

Time O(n) — every node is visited once. Space O(n) for the collected values, plus the traversal stack.

Open bounds

You don't need to store the whole traversal. Give each recursive call an open bound: a limit the node must stay strictly above or below. When you move left, the current value becomes the new upper bound. When you move right, it becomes the new lower bound.

def is_valid_bst(root: TreeNode | None) -> bool:
    def valid(node: TreeNode | None, low: int | None, high: int | None) -> bool:
        if node is None:
            return True
        if low is not None and node.val <= low:
            return False
        if high is not None and node.val >= high:
            return False
        return (
            valid(node.left, low, node.val)
            and valid(node.right, node.val, high)
        )
 
    return valid(root, None, None)

The bounds come from every ancestor on the path. That's why a value that looks fine beside its parent can still be rejected for crossing the root's boundary. Using None instead of made-up numeric sentinels also keeps both signed 32-bit extremes valid.

Time O(n) — each node is checked once. Space O(h) for the recursive stack, where h is the tree's height.