Validate Binary Search TreeMedium

Given the root of a binary tree, determine if it is a valid Binary Search Tree: every node's left subtree must contain only values less than the node, right subtree only values greater.

Examples

A tree where every immediate parent-child pair looks ordered, but a deeper node breaks the rule relative to an ancestor further up → false

Approach

The tempting-but-wrong approach only compares each node to its immediate children — that misses violations against ancestors further up the tree (see the code for a concrete broken case). The correct approach carries a valid (min, max) RANGE down as you recurse: every node must fall strictly within the range set by all its ancestors, not just its direct parent. Going left tightens the max to the current value; going right tightens the min.

Complexity — best & worst case

Time O(n) worst case (valid tree, must check every node), O(1) best case (root itself immediately violates the range)

Space O(h) — recursion depth equals tree height, O(n) worst case for a completely unbalanced tree

Code

// Given the root of a binary tree, determine if it is a valid Binary
// Search Tree: every node's left subtree must contain only values
// LESS than the node, right subtree only values GREATER.

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

// --- Wrong-but-tempting approach: only check immediate children ---
// This FAILS for cases like [5,1,4,null,null,3,6] — node 3 is less
// than root 5 but it's in the right subtree, which is invalid. You
// have to carry a valid RANGE down through the whole subtree, not
// just compare parent-to-child.
function isValidBSTNaive(root) {
  if (!root) return true;
  if (root.left && root.left.value >= root.value) return false;
  if (root.right && root.right.value <= root.value) return false;
  return isValidBSTNaive(root.left) && isValidBSTNaive(root.right);
}

// --- Correct: pass down a valid (min, max) range as you recurse ---
function isValidBST(root, min = -Infinity, max = Infinity) {
  if (!root) return true;
  if (root.value <= min || root.value >= max) return false;

  return (
    isValidBST(root.left, min, root.value) &&
    isValidBST(root.right, root.value, max)
  );
}

// --- Example Usage ---
const valid = new TreeNode(2, new TreeNode(1), new TreeNode(3));
console.log("valid BST:", isValidBST(valid)); // true

// The classic trap: every PARENT-CHILD pair looks fine in isolation
// (4 < 5, 6 > 5, 3 < 6, 7 > 6) but node 3 sits in root 5's right
// subtree, where every value must be > 5. Node 3 breaks that even
// though its immediate parent (6) never notices.
//         5
//        / \
//       4   6
//          / \
//         3   7
const invalid = new TreeNode(5,
  new TreeNode(4),
  new TreeNode(6, new TreeNode(3), new TreeNode(7)),
);
console.log("invalid BST:", isValidBST(invalid)); // false (3 must be > 5, but isn't)
console.log("naive check misses it:", isValidBSTNaive(invalid)); // true — the bug in action