Validate Binary Search Tree

Validate Binary Search Tree is the problem that exposes whether you really understand the BST rule. Most people get it almost right — and the "almost" is exactly what interviewers probe.

The slow way first

The tempting (wrong) approach: at each node, just check left.val < node.val < right.val. That only compares a node to its direct children — it misses violations deeper down. In our example 8's children look locally fine (4 < 8 < 9), yet 4 still breaks the rule relative to its grandparent 5.

A correct-but-clumsy fix is to scan the entire subtree at each node to confirm the bound — that is O(n²). We can do far better.

The idea: carry a (low, high) window

Instead of looking down, push an allowed window down. Each node is only valid if low < val < high. As we recurse:

• going left, the value becomes the new upper bound (high = node.val),
• going right, the value becomes the new lower bound (low = node.val).

The root starts with the widest possible window: (-inf, +inf).

The key insight: the window remembers every ancestor at once. By the time we reach 4, its window is (5, 8) — 5 from being in the right subtree of the root, 8 from being the left child of 8. So 4 is checked against 5, not just its parent.

Walk through it

Step through the animation. The active node lights up as DFS descends; the bounds label shows the live window. Root 5 passes with (-inf, +inf), 3 passes with (-inf, 5), 8 passes with (5, +inf). Then we reach 4 with window (5, 8) — and 4 is not greater than 5, so the check fails. The function returns False immediately; node 9 is never even visited.

Pseudocode

valid(node, low, high):
    if node is empty:
        return True                       # an empty tree is a valid BST
    if not (low < node.val < high):
        return False                      # node falls outside its window
    return valid(node.left,  low, node.val)   # left: tighten the high bound
       and valid(node.right, node.val, high)  # right: tighten the low bound
 
answer = valid(root, -infinity, +infinity)

The Python solution

def is_valid_bst(root):
    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, float("-inf"), float("inf"))

• valid(node, low, high) asks: is the subtree at node a BST whose every value lies in (low, high)?
• An empty node is trivially valid — that is the base case that stops the recursion.
• Line 5 is the whole algorithm: a single strict range check, low < val < high.
• Recursing left passes node.val as the new high; recursing right passes it as the new low. This is how the window inherits all ancestor constraints.
• The and short-circuits: the moment one bound breaks, we stop and return False.

Complexity

We visit each node exactly once, so time is O(n). Space is O(h) for the recursion stack, where h is the tree height — O(log n) for a balanced tree, O(n) for a degenerate one.

When this pattern shows up

Practice