Validate BST

Signal

"Is this a valid X" where X has a global ordering property is a giveaway that checking only the immediate parent-child relationship isn't enough — you need bounds threaded down from every ancestor, tightening as you go.

Approach

Recurse carrying a (low, high) range. A node's value must fall strictly inside that range; when recursing left, tighten the upper bound to the current node's value; when recursing right, tighten the lower bound.

Skeleton

def valid(node, low, high):
    if not node: return True
    if not (low < node.val < high): return False
    return valid(node.left, low, node.val) and valid(node.right, node.val, high)
return valid(root, -inf, inf)

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


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

    return valid(root, float('-inf'), float('inf'))

Complexity

O(n) time — every node visited once. O(h) recursion stack space.

Pitfalls

• Comparing a node only to its direct children passes for trees that are locally sorted but globally invalid — a node in the left subtree can be larger than the root while still being smaller than its immediate parent. Bounds must come from every ancestor, not just one.
• Values must be strictly between bounds — this problem's BST doesn't allow duplicates equal to an ancestor's value.
• An iterative in-order traversal that checks each visited value is strictly greater than the previous one is an equally valid, arguably simpler, alternative worth knowing.