98. Validate Binary Search Tree

Almost everyone gets this problem almost right on the first try — they compare each node to its two children and call it done. That version passes the obvious tests and fails the moment a value sneaks past a distant ancestor. Getting it right is the point of the problem, and it’s a clean entry into the binary tree patterns that reward thinking about a whole subtree at once.

The problem

Given the root of a binary tree, decide whether it’s a valid binary search tree: every node in a node’s left subtree must be smaller than it, everything in the right subtree must be larger, and that has to hold all the way down. (Full statement on LeetCode.)

The tree below looks fine locally — 4 is less than 6, 7 is greater — but it isn’t a valid BST:

      6
     / \
    4   7
       / \
      3   9

3 sits in the right subtree of 6, so it must be greater than 6. It isn’t. A check that only compares 7 to 3 and 9 never catches it.

Intuition: every node lives inside a shrinking window

The fix is to stop thinking about parent-and-child and start thinking about range. Each node isn’t just constrained by its parent — it’s constrained by every ancestor it hangs under. So carry a valid open interval $(\text{low}, \text{high})$ down the tree, and require each node’s value to fall strictly inside it.

The root can be anything, so it starts with the widest possible window, $(-\infty, +\infty)$. When you step left, the current node becomes a new upper bound — everything on the left must be smaller. When you step right, it becomes a new lower bound. That’s the whole idea:

$\text{left child} \in (\text{low},\ \text{node}) \qquad \text{right child} \in (\text{node},\ \text{high})$

Back to the broken tree: descending 6 → 7 → 3, the window tightens to $(6, 7)$, and 3 is nowhere near it. The violation is caught exactly where the naive check missed it, because the bound from 6 traveled down with the recursion.

Solution

One catch before the code: node values can be as large as Integer.MAX_VALUE or as small as Integer.MIN_VALUE. If you seed the bounds with int, a legitimate root of Integer.MIN_VALUE would fail its own comparison. Using long bounds sidesteps the overflow entirely.

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

    // Each node must fall strictly inside the (low, high) window
    // inherited from all of its ancestors.
    private boolean validate(TreeNode node, long low, long high) {
        if (node == null) return true;                 // empty subtree is valid
        if (node.val <= low || node.val >= high) return false;

        // Going left tightens the ceiling; going right raises the floor.
        return validate(node.left, low, node.val)
            && validate(node.right, node.val, high);
    }
}

There’s a second, equally clean way to see it: an inorder traversal of a valid BST visits values in strictly increasing order. Walk the tree inorder, keep the previously seen value, and the instant the sequence stops rising, it’s invalid. Both are $O(n)$; the bounds version is the one I reach for because it fails fast and reads like the definition.

Complexity

	Time	Space
Bounds recursion	$O(n)$	$O(h)$

You touch each node once, so time is linear. Space is the recursion stack, $O(h)$ for tree height — $O(\log n)$ when the tree is balanced, but $O(n)$ in the worst case of a degenerate, list-like tree.

In an interview

Say the trap out loud before you write anything: “comparing a node only to its children is wrong, because a value can satisfy its parent but still violate an ancestor.” That one sentence tells the interviewer you already see the failure case they were going to spring on you. Then introduce the $(\text{low}, \text{high})$ window and mention the long-bounds detail — the overflow edge is a favorite follow-up.

If they ask for an alternative, the inorder-is-sorted framing connects straight to Kth Smallest Element in a BST, which leans on the same ordered walk. The recursive “check a property over both subtrees” shape also mirrors Same Tree; the binary tree pattern hub collects where this recursion recurs.

References

• LeetCode 98 — Validate Binary Search Tree