Validate Binary Search Tree

Examples

Input: root = [2,1,3]
Output: true

1 < 2 < 3, and the property holds everywhere.

Input: root = [10,5,15,null,null,6,20]
Output: false

6 sits in 10's right subtree (as the left child of 15), but 6 is less than 10. Comparing 6 only to its parent 15 would miss this — the whole right subtree must stay greater than 10.

Input: root = [5,4,6,null,null,3,7]
Output: false

3 is in 5's right subtree (under 6), but 3 is less than 5.

Constraints

• The number of nodes is in the range [1, 10^4].

• Node values are in the range [-2^31, 2^31 - 1].

Approach

The key mistake is checking a node only against its immediate children — that misses violations that come from further up the tree. Instead, each node must fall within a valid range determined by its ancestors: a left child must be less than its parent and still within whatever upper bound the parent inherited, and similarly for right children.

A different way to see the same idea: an in-order traversal (left, node, right) of a valid BST visits values in strictly increasing order. So checking that the in-order sequence never goes flat or backwards is an equally valid test.

Solutions

Brute Force — In-Order Traversal into an Array

Collect every value via an in-order traversal (left, node, right). If the tree really is a valid BST, this sequence must come out strictly increasing. So after collecting it, just walk through and confirm each value is bigger than the one before it.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function isValidBST(root) {
  const values = [];

  function inorder(node) {
    if (node === null) return;
    inorder(node.left);
    values.push(node.val);
    inorder(node.right);
  }

  inorder(root);

  for (let i = 1; i < values.length; i++) {
    if (values[i] <= values[i - 1]) return false;
  }
  return true;
}

Time: O(n) · Space: O(n) — storing every value in an array

Optimal — Recursive Range Checking

Give every node a valid range (lower, upper) it must fall strictly inside, inherited from its ancestors. The root's range is unbounded. When you move into a left child, that child's upper bound tightens to the parent's value (it must stay less than the parent). When you move into a right child, its lower bound tightens to the parent's value instead. If any node ever falls outside its inherited range, the tree is invalid.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function isValidBST(root) {
  function validate(node, lower, upper) {
    if (node === null) return true;
    if (lower !== null && node.val <= lower) return false;
    if (upper !== null && node.val >= upper) return false;

    return validate(node.left, lower, node.val) && validate(node.right, node.val, upper);
  }

  return validate(root, null, null);
}

Time: O(n) · Space: O(h) — recursion stack, where h is the tree's height