Validate Binary Search Tree

mediumTests passed 2026-11-11v1.0.0
TC: O(N)|SC: O(H)
TreesOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Propagate an open validity interval `(lo, hi)` down the recursion: moving left narrows upper bound to `node.val`, moving right narrows lower bound to `node.val`. Strictly enforce `lo < node.val < hi`.

2. Complexity Bounds & Proof

Checks every node against exact ancestral upper/lower constraints once in pre-order DFS.

3. Minimal Idiomatic Code

def isValidBST(root: Optional[TreeNode]) -> bool:
    def valid(node, lo, hi):
        if not node:
            return True
        if not (lo < node.val < hi):
            return False
        return valid(node.left, lo, node.val) and valid(node.right, node.val, hi)
    return valid(root, float('-inf'), float('inf'))

4. Failure Modes & Interview Follow-ups

Pitfalls:- Only checking `left.val < node.val < right.val` misses invalid deep right-left grandchildren (e.g., `6` in left subtree of `5`). - Using 32-bit `INT_MIN`/`INT_MAX` sentinels breaks on extreme leaf values; use `int64` / `float("inf")` / nullable bounds.
Follow-ups:- Iterative inorder traversal checking strictly increasing previous value runs in the same time/space.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Lowest Common Ancestor of a Binary Search Tree (O(H))Kth Smallest Element in a BST (O(H + k))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.