Validate Binary Search Tree

MEDIUM✓ CHIP-TIMEDLC #98 — FULL STATEMENT ↗

The drill: Check whether a binary tree is a true BST — not just locally sane at each node, but consistent with every ancestor above it, all the way to the root.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A binary tree arrives, and the job is deciding whether it truly satisfies the BST property everywhere, not just between neighboring nodes.

Local sanity — left child smaller, right child bigger — isn't sufficient on its own; a node several levels down must still respect every ancestor's ordering, not merely its direct parent.

Equal values anywhere in the tree break the strict ordering the same way a misplaced value would, so the verdict is a single yes-or-no: true if the whole structure is a valid BST end to end, false the moment any node breaks the ordering inherited from above.

EX 01

root = []

→ true

EMPTY TREE, VACUOUSLY VALID

EX 02

root = [2, 1, 3]

→ true

CANONICAL VALID BST

EX 03

root = [5, 1, 4, null, null, 3, 6]

→ false

LOCALLY SANE, GLOBALLY BROKEN

node counts run from a handful up to tens of thousands
values span the full range of ordinary integers
equal values anywhere in the tree break the strict ordering
the verdict is a single boolean covering the entire tree

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Checking only "left child smaller, right child bigger" at each node isn't enough — a node three levels down can violate an ancestor two levels above its own parent.

HINT 2 THE STRUCTURE

Every node actually lives inside a valid range, and that range is set by the whole chain of ancestors above it, not just its direct parent.

HINT 3 ONE STEP FROM THE ANSWER

Carry (low, high) bounds downward: going left tightens the high bound to the current value, going right tightens the low bound. A node fails the instant it falls outside its inherited range.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE SHRINKING WINDOWPATTERN · BOUNDS PROPAGATIONroot = [5, 1, 4, null, null, 3, 6]

STEP 1

Local sanity — left smaller, right bigger — isn't enough. Every node must respect the FULL chain of ancestor bounds.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/validate-binary-search-tree.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def valid(node: Optional[TreeNode], low: float, high: float) -> bool:
            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, float("-inf"), float("inf"))

TIME O(N)SPACE O(H)PYTHON · RACE PACE · 10 LN

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def all_less(node: Optional[TreeNode], val: int) -> bool:
            if not node:
                return True
            return node.val < val and all_less(node.left, val) and all_less(node.right, val)

        def all_greater(node: Optional[TreeNode], val: int) -> bool:
            if not node:
                return True
            return node.val > val and all_greater(node.left, val) and all_greater(node.right, val)

        def valid(node: Optional[TreeNode]) -> bool:
            if not node:
                return True
            if not all_less(node.left, node.val):
                return False
            if not all_greater(node.right, node.val):
                return False
            return valid(node.left) and valid(node.right)

        return valid(root)

TIME O(N²)SPACE O(N)PYTHON · TRAINING PACE · 22 LN

class Solution {
    public boolean isValidBST(TreeNode root) {
        return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean valid(TreeNode node, long low, long high) {
        if (node == null) {
            return true;
        }
        if (!(low < node.val && node.val < high)) {
            return false;
        }
        return valid(node.left, low, node.val) && valid(node.right, node.val, high);
    }
}

TIME O(N)SPACE O(H)JAVA · RACE PACE · 15 LN

class Solution {
    public boolean isValidBST(TreeNode root) {
        return valid(root);
    }

    private boolean valid(TreeNode node) {
        if (node == null) {
            return true;
        }
        if (!allLess(node.left, node.val) || !allGreater(node.right, node.val)) {
            return false;
        }
        return valid(node.left) && valid(node.right);
    }

    private boolean allLess(TreeNode node, long val) {
        if (node == null) {
            return true;
        }
        return node.val < val && allLess(node.left, val) && allLess(node.right, val);
    }

    private boolean allGreater(TreeNode node, long val) {
        if (node == null) {
            return true;
        }
        return node.val > val && allGreater(node.left, val) && allGreater(node.right, val);
    }
}

TIME O(N²)SPACE O(N)JAVA · TRAINING PACE · 29 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED