Validate Binary Search Tree

1. Define the problem

Given the root of a binary tree (as a level-order array with null for a missing child), determine whether it is a valid binary search tree . Use recursion passing down a (low, high) range that narrows with every step: the base case is an empty subtree, which is always valid. The recursive case checks the current node against its range, then recurses into each child with an updated bound.

Constraints

The number of nodes in the tree is in the range [1, 10⁴]
-2³¹ ≤ Node.val ≤ 2³¹ - 1

Example

Inputroot = [5, 1, 4, null, null, 3, 6]

Outputfalse

Explanation Node 4 sits in the root's right subtree, so every value there must be greater than 5 — 4 is not, so the tree is invalid.

2. Know the words first

In plain terms

Bound: A lower or upper limit a node's value must respect, inherited from an ancestor higher up the tree — not just its immediate parent.
Level order: Listing tree node values top-to-bottom, left-to-right, the way LeetCode serializes trees, with null standing in for a missing child.

3. Visualize the solution

Recurse with a shrinking (low, high) range

3·

4·

Statusvalidate(5, -∞, ∞)

Root value 5 is within (-∞, ∞). Recurse left with range (-∞, 5) and right with range (5, ∞).

What happens in this step

validate(5, -Infinity, Infinity)

5 is strictly between -Infinity and Infinity, so this node passes. Recurse left into node 1 with range (-Infinity, 5), and right into node 4 with range (5, Infinity).

Step 1 of 5

Steps to visualize

Start at the root with an unbounded range: (-Infinity, Infinity).
Check the current node's value falls strictly inside its (low, high) range — if not, the whole tree is invalid.
Recurse into the left child with an updated upper bound of the current value.
Recurse into the right child with an updated lower bound of the current value.
An empty subtree is the base case — it always satisfies any range.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Recurse with a shrinking (low, high) range

3·

4·

Statusvalidate(5, -∞, ∞)

Root value 5 is within (-∞, ∞). Recurse left with range (-∞, 5) and right with range (5, ∞).

What happens in this step

validate(5, -Infinity, Infinity)

5 is strictly between -Infinity and Infinity, so this node passes. Recurse left into node 1 with range (-Infinity, 5), and right into node 4 with range (5, Infinity).

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function isValidBST(values) {
  function buildTree(arr) {
    if (!arr || arr.length === 0 || arr[0] === null) return null;

    const root = { val: arr[0], left: null, right: null };
    const queue = [root];
    let i = 1;

    while (queue.length > 0 && i < arr.length) {
      const node = queue.shift();

      if (i < arr.length) {
        const leftVal = arr[i++];
        if (leftVal !== null && leftVal !== undefined) {
          node.left = { val: leftVal, left: null, right: null };
          queue.push(node.left);
        }
      }
      if (i < arr.length) {
        const rightVal = arr[i++];
        if (rightVal !== null && rightVal !== undefined) {
          node.right = { val: rightVal, left: null, right: null };
          queue.push(node.right);
        }
      }
    }

    return root;
  }

  function validate(node, low, high) {
    if (node === null) {
      return true; // base case
    }
    if (node.val <= low || node.val >= high) {
      return false;
    }
    return validate(node.left, low, node.val) && validate(node.right, node.val, high); // recursive case
  }

  return validate(buildTree(values), -Infinity, Infinity);
}

Time: O(n)
Space: O(h)

6. Test cases

Test cases

Input	Expected	Covers
`root = [5, 1, 4, null, null, 3, 6]`	`false`	example from the docstring
`root = [2, 1, 3]`	`true`	smallest non-trivial valid tree
`root = [1]`	`true`	base case, a single node is trivially valid
`root = [2, 2, 2]`	`false`	a BST requires strictly smaller/greater, so equal values are invalid
`root = [3, 2, null, 1]`	`true`	a valid left-leaning chain, several calls deep
`root = [10, 5, 15, null, null, 6, 20]`	`false`	a node that looks fine locally but violates a bound inherited from higher up (6 is less than the root's 10)
`root = [4, 2, 6, 1, 3, 5, 7]`	`true`	a balanced valid tree with recursion on both sides

Validate Binary Search Tree