Validate Binary Search Tree With Shrinking Bounds

"Validate Binary Search Tree" shows up again and again in Amazon, Meta, Microsoft phone screens. It is a Medium problem on paper, but the real test is whether you recognize the Tree DFS pattern quickly and code it cleanly. Part 8 of 11 in the Tree DFS arc.

The Problem

Determine whether a binary tree is a valid BST: every node in a left subtree below the ancestor's value, every node in a right subtree above it, both subtrees valid. The famous trap — checking only parent against children — passes shallow tests and fails deep ones, which is exactly why this question persists.

Input:  root = [5, 1, 4, None, None, 3, 6]
Output: False
The 3 sits in the right subtree of 5 — invalid regardless of its parent 4.

Recognizing the Tree DFS Pattern

Depth-first search commits to one branch before trying siblings — recursion (or an explicit stack) whose call structure mirrors the tree itself. Its natural questions are about paths (root to leaf), subtree properties (computed bottom-up from children), and exhaustive exploration (islands, connected regions). The recurring design decision is what each recursive call returns versus what it accumulates in shared state.

BST validity is a constraint between a node and all its ancestors, not just its parent. Constraints that accumulate along the root path are threaded state: each node lives in an interval (low, high) narrowed by every ancestor turn.

The Approach

Recurse with bounds: start with infinities; going left tightens the upper bound to the node's value, going right tightens the lower. A node violating its interval fails immediately. Strict inequalities — duplicates are invalid under the standard definition.

The elegant alternative: an in-order traversal of a BST is strictly increasing, so validate by tracking the previous in-order value. Both are O(n); knowing both lets you match whichever the interviewer leans toward.

Python Solution

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


def is_valid_bst(root: TreeNode | None) -> bool:
    """True if the tree satisfies the strict BST invariant."""

    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

• Time: O(n) — each node is checked against its interval once
• Space: O(h) — recursion stack

Interview Tips and Follow-Ups

• The deep-violation case ([5, 4, 6, None, None, 3, 7]) is mandatory in your own test list — it is the case the naive solution passes over.
• Duplicates: strict less-than is the default; if the interviewer allows equals-on-one-side, one comparison changes. Ask.
• Integer sentinels break when node values include the extremes — float infinities (or None bounds) sidestep it; this is a real Amazon follow-up.

If this clicked, continue the Tree DFS arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.