Validate Binary Search Tree

MediumTreesTreeDFSBinary Search Tree

Problem

Given a binary tree, decide whether it is a valid binary search tree: every node's value must exceed all values in its left subtree and be less than all values in its right subtree, and this must hold for every descendant, not only the immediate children.

Example. A tree with root 5, left child 3, right child 8, where 3 has a right child 7, looks locally fine at each parent-child pair, but is invalid overall: 7 sits inside the root's left subtree yet exceeds the root's value of 5.

Key idea

The naive check compares each node only to its direct children (is the left child smaller, is the right child larger), but that misses violations further down, exactly as in the example above, where the problem node is a grandchild.

The fix is to track a valid range, a lower and upper bound, that must contain each node's value, narrowing that range while descending. The root starts unbounded; recursing left tightens the upper bound to the parent's value, recursing right tightens the lower bound. Any node whose value falls outside its inherited range makes the tree invalid. An equivalent approach: a binary search tree's in-order traversal visits values in strictly increasing order, so comparing each visited value only to the one before it detects any violation just as reliably.

Solution

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

function isValidBST(root: TreeNode | null): boolean {
  function inRange(node: TreeNode | null, lower: number | null, upper: number | null): boolean {
    if (node === null) {
      return true;
    }
    // Strict comparisons reject duplicate values on either side.
    if (lower !== null && node.val <= lower) {
      return false;
    }
    if (upper !== null && node.val >= upper) {
      return false;
    }
    // Descending left tightens the upper bound; descending right tightens the lower bound.
    return inRange(node.left, lower, node.val) && inRange(node.right, node.val, upper);
  }

  // Null bounds mean no constraint yet, so the root starts unbounded.
  return inRange(root, null, null);
}

Complexity

  • Time: O(n). Every node is visited once.
  • Space: O(h). The recursion stack, where h is the tree's height.

Watch out for

  • Checking only immediate children, not the full inherited range, is the classic bug that misses deeper violations.
  • Use strict inequalities on both bounds; this definition disallows duplicate values in either subtree.
  • If node values can reach the edges of the representable range, use nullable sentinels for "no bound yet" rather than an in-range value as a stand-in for infinity.

Pattern

This is the "narrow the valid range while descending" pattern, sometimes called a min/max bound recursion. It also underlies validating any structure that must stay monotonic along a path.

Related questions