#103

Validate Binary Search Tree

medium

treedepth-first-searchbinary-search-treebinary-tree

Given the root of a binary tree, return true if it is a valid binary search tree.

A tree is a valid BST when, for every node, all values in its left subtree are strictly less than the node's value and all values in its right subtree are strictly greater. The constraint is global, not just parent-to-child: a node deep in a right subtree still must respect every ancestor's bound.

The tree is given as a level-order array where null marks a missing child: [2, 1, 3] is root 2 with children 1 and 3.

Example

Input: root = [2,1,3]123

Output: true

1 < 2 < 3.

Constraints

The number of nodes in the tree is in the range [1, 10^4].
-2^31 <= Node.val <= 2^31 - 1

Intuition

A BST requires that for every node, all left-subtree values are smaller and all right-subtree values are larger — a global rule, not just parent-to-child. The cleanest brute force leans on that: an in-order traversal of a valid BST is strictly increasing, so collect the in-order values and check they're sorted.

function isValidBST(root) {
  const vals = [];
  const inorder = (node) => {
    if (!node) return;
    inorder(node.left);
    vals.push(node.val);
    inorder(node.right);
  };
  inorder(root);
  // A valid BST's in-order sequence is strictly increasing.
  for (let i = 1; i < vals.length; i++) {
    if (vals[i] <= vals[i - 1]) return false;
  }
  return true;
}

Brute force — in-order into an array, then verify it's strictly increasing: O(n) time, O(n) space.

Correct and O(n), but it materializes the whole value array and can't bail out the instant it sees a violation high in the tree. Can we validate in place?

The key observation: each node lives inside an open interval (low, high) set by its ancestors. Descending left tightens the upper bound to the parent's value; descending right tightens the lower bound. A node is valid iff it lies strictly inside its interval — strict comparisons reject duplicates. This catches the global-violation case (a node that respects its parent but breaks a distant ancestor's bound) that a naive parent-only check misses.

Tracing [5, 1, 4, null, null, 3, 6] — root 5, left 1, right 4 with children 3, 6:

Root 5: interval (-∞, +∞) — fine.
Left child 1: interval (-∞, 5) — 1 < 5, fine.
Right child 4: interval (5, +∞) — but 4 is not > 5. Violation: 4 sits in 5's right subtree yet is smaller than 5. Return false immediately, without inspecting 3 or 6.

The bound is inherited, not local: a node deep in a right subtree must still exceed every ancestor it descended right from — that's why a parent-only check is wrong.
Strict </> (not <=/>=) is what rejects duplicate values, which a BST disallows.
No lane — the validity test threads a shrinking (low, high) interval down the recursion, a per-node bound a single scanned row can't carry.

Optimization

Bounded recursion

Recurse with an open interval (low, high) each node must lie strictly within. The root starts unbounded; descending left tightens the upper bound to the node's value, descending right tightens the lower bound. Using strict comparisons rejects duplicates. This catches the global-violation case a naive parent-only check misses.

O(n) time, O(h) recursion space.

function isValidBST(root) {
  const valid = (node, low, high) => {
    if (!node) return true;
    if ((low !== null && node.val <= low) || (high !== null && node.val >= high)) return false;
    return valid(node.left, low, node.val) && valid(node.right, node.val, high);
  };
  return valid(root, null, null);
}

Complexity analysis

Time complexity: O(n). Here's why:

The bounded recursion visits each node once, doing an O(1) interval check.

So O(n), short-circuiting on the first violation.

Space complexity: O(h). Here's why:

Only the recursion stack — depth h.

O(log n) balanced, O(n) worst case. No in-order array is materialized.

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
root = [9]9	true	Single node is a valid BST.
root = [8,4,12]4812	true	4 < 8 < 12 — valid.
root = [8,2,7,null,null,6,9]28679	false	7 is in 8's right subtree but 7 < 8 — global violation.
root = [3,3,3]333	false	Duplicates break the strict ordering.
root = [20,10,30,null,null,15,40]1020153040	false	15 sits in 20's right subtree but is less than 20.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor