Validate Binary Search Tree

The problem. Given the root of a binary tree, return true if it is a valid binary search tree: every node's left subtree holds only values less than the node, its right subtree only values greater, and both subtrees are BSTs too.

Example

root = [2, 1, 3]                     ->  true
root = [5, 1, 4, null, null, 3, 6]   ->  false   (4 is in 5's right subtree)
root = [5, 1, 6, null, null, 3, 7]   ->  false   (3 is in 5's right subtree)
root = [2, 2, 2]                     ->  false   (no duplicates: strictly less / greater)

The trap

Checking only left.val < node.val < right.val at each node passes the tree above — and it's wrong. The rule is about whole subtrees. Two correct ways to enforce it: pass down the range each node must fit in, or check that the in-order walk is strictly increasing.

1. Brute force: compare with every value below

At each node, check that the largest value in its left subtree is smaller and the smallest value in its right subtree is bigger — then check both subtrees the same way.

1function isValidBST(node) {2  if (node === null) return true;3  if (node.left !== null && max(node.left) >= node.val) return false;4  if (node.right !== null && min(node.right) <= node.val) return false;5  return isValidBST(node.left) && isValidBST(node.right);6}7 8function max(n) {                                // the largest value in this subtree9  let m = n.val;10  if (n.left !== null) m = Math.max(m, max(n.left));11  if (n.right !== null) m = Math.max(m, max(n.right));12  return m;13}14 15function min(n) {                                // the smallest value in this subtree16  let m = n.val;17  if (n.left !== null) m = Math.min(m, min(n.left));18  if (n.right !== null) m = Math.min(m, min(n.right));19  return m;20}

Time O(n²) in the worst case (every node scans its whole subtree), space O(h).

2. Pass down the allowed range

The root may be anything. Going left narrows the range from above (everything there must be below this node); going right narrows it from below. Each node just checks that it fits its range.

1function isValidBST(root) {2  const fits = (node, low, high) => {        // every value here must be strictly between low and high3    if (node === null) return true;4    if (node.val <= low || node.val >= high) return false;5    return fits(node.left, low, node.val) && fits(node.right, node.val, high);6  };7  return fits(root, -Infinity, Infinity);8}

Time O(n), space O(h). Java and C++ use 64-bit bounds because a node may hold Integer.MIN_VALUE or MAX_VALUE itself.

3. In-order must be strictly increasing

A binary tree is a BST exactly when its in-order walk is strictly increasing. Walk it and compare each value with the previous one.

1function isValidBST(root) {2  let prev = null;3  const inorder = (node) => {4    if (node === null) return true;5    if (!inorder(node.left)) return false;6    if (prev !== null && node.val <= prev) return false;   // not bigger than the value before it7    prev = node.val;8    return inorder(node.right);9  };10  return inorder(root);11}

Time O(n), space O(h). It stops at the first value out of order.

Comparing the approaches

Edge cases to test

Variations