Validate Binary Search Tree

Difficulty: Medium

Problem

Given the root of a binary tree, determine if it is a valid binary search tree (BST): every node's ENTIRE left subtree contains only values LESS than the node, every node's ENTIRE right subtree contains only values GREATER, and both subtrees are themselves valid BSTs. The word 'entire' is where everyone gets caught.

Example

Input: root = [5,4,6,null,null,3,7]
Output: false
Explanation: Node 3 looks fine next to its parent 6 (3 < 6 ✓). But 3 sits inside 5's RIGHT subtree, where everything must be GREATER than 5 — and 3 isn't. Not a BST.

Brute-force approach

The tempting parent-child-only check is not a slower solution — it's a WRONG one. The lesson shows exactly how it fails, then fixes it with ranges.

Optimal approach

Key insight: Every turn you take on the way down leaves a promise. The (lo, hi) range remembers ALL of them — one comparison per node checks every ancestor at once.

Pass an allowed (lo, hi) range down the tree. Each node must sit strictly inside its range; going left tightens the ceiling, going right raises the floor.

Steps

  1. Start at the root with the wide-open range (-∞, +∞)
  2. At each node check: lo < node.val < hi; if not, return false
  3. Recurse left with (lo, node.val) — the ceiling drops
  4. Recurse right with (node.val, hi) — the floor rises
  5. Null subtrees are valid (they break no promises)

Time complexity: O(n) · Space complexity: O(h) where h = height of tree