Validate Binary Search Tree

Return true if a binary tree is a valid binary search tree: every node's left subtree holds only smaller values and its right subtree only larger ones. No duplicates. (LC 98)

Max Depth teaches tree DFS where information flows up (each node returns a depth). This one flows down: each node is handed the range it is allowed to be in.

The recipe

Say before you type: "It isn't enough to compare a node to its parent. A node deep in the right subtree has to beat the root too. So I pass down a lower and an upper bound. Going left, the current value becomes the new upper bound. Going right, it becomes the new lower bound."

1. Start with the range (-Infinity, Infinity) at the root.
2. An empty node is valid.
3. If node.val <= lo or node.val >= hi, it is invalid. Both comparisons are strict, so duplicates fail.
4. Recurse left with (lo, node.val) and right with (node.val, hi). Both sides must be valid.

The code

function isValidBST(root: TreeNode | null): boolean {
  const check = (node: TreeNode | null, lo: number, hi: number): boolean => {
    if (!node) return true;
    if (node.val <= lo || node.val >= hi) return false; // strict: no duplicates
    return check(node.left, lo, node.val) && check(node.right, node.val, hi);
  };
  return check(root, -Infinity, Infinity);
}

Why this shape

A binary search tree is not defined by parent-child pairs. It is defined by whole subtrees: everything to the left of a node is smaller, all the way down. The bounds are how that rule travels. When you go right from 5 and then left from 7, the range is (5, 7), so a 3 down there is wrong even though it is smaller than its own parent.

The other answer: in-order is sorted

An in-order walk of a valid BST visits values in strictly increasing order. So walk in order and check that each value beats the previous one.

function isValidBST(root: TreeNode | null): boolean {
  const stack: TreeNode[] = [];
  let cur = root, prev = -Infinity;
  while (cur || stack.length) {
    while (cur) { stack.push(cur); cur = cur.left; }
    cur = stack.pop()!;
    if (cur.val <= prev) return false;
    prev = cur.val;
    cur = cur.right;
  }
  return true;
}

It needs no bounds, and it is the one that makes the problem feel obvious in hindsight. Mention both.

Complexity

	Cost	Because
Time	O(n)	Every node is checked once
Space	O(h)	The recursion (or the stack) goes as deep as the tree is tall

Traps

• Only comparing with the parent. [5, 4, 6, null, null, 3, 7] passes every parent-child check, and it is still invalid, because 3 is in the right subtree of 5. This is the bug the problem is built around.
• Non-strict comparisons. A BST here does not allow duplicates, so [1, 1] and [2, 2, 2] are invalid. < where you need <= lets them through.
• Using Integer.MIN_VALUE as the first bound. A node holding exactly -2147483648 fails against a bound of -2147483648. Start from -Infinity and Infinity, or null bounds, so no real value can collide.
• An empty tree is valid. Return true for null, not false.
• Checking only one side. Both check calls must hold. && between them is not optional.

The pattern this trains

Tree recursion comes in two flavours: information flows up (Max Depth, Diameter, Balanced Tree) or flows down (this, Path Sum, Count Good Nodes). Ask yourself which one the problem needs, then decide the parameters or the return value. The BST property also unlocks Kth Smallest Element in a BST (230, an in-order walk that stops early), Lowest Common Ancestor of a BST (235) and Recover Binary Search Tree (99).