LeetCode 98 · DFS · Binary Search Tree

Validate Binary Search Tree

MediumCheck that a tree is a BST using an allowed (low, high) range per node.
Given the root of a binary tree, determine whether it is a valid binary search tree (BST). In a valid BST, a node’s ENTIRE left subtree contains only smaller values, its ENTIRE right subtree only larger values, and both subtrees are themselves BSTs.

Walkthrough

try:
LeetCode array format. A valid BST needs every node in its left subtree smaller and every node in its right subtree larger — not just its direct children.
1
function isValidBST(root) {
2
  function valid(node, low, high) {
3
    if (!node) return true;
4
    if (node.val <= low || node.val >= high) return false;
5
    return valid(node.left,  low,      node.val)
6
        && valid(node.right, node.val, high);
7
  }
8
  return valid(root, -Infinity, Infinity);
◄
9
}
current range
(−∞, +∞)
call stack (root → current)
—
step 0 / 10
213
checkingin range ✓out of range ✗
STEP 0 / 10 · line 8
Start with no bounds
Every node must fall inside an allowed (low, high) range. The root can be anything, so start with (−∞, +∞). Each step tightens the range for the subtree below.

Intuition

The common mistake is checking only node.val vs its direct children. That misses violations like a small value buried deep in a right subtree — it must still exceed every ancestor it branched right from.

Instead, carry an allowed open range (low, high) down the recursion. The root may be anything, so it starts as (−∞, +∞).

A node is valid only if low < node.val < high. When you descend left, the value becomes the new upper bound; when you descend right, it becomes the new lower bound.

If any node falls outside its range, the whole tree fails. If every node fits, it is a valid BST.

The algorithm

  1. 01Call valid(root, −∞, +∞).
  2. 02A null node is trivially valid → return true.
  3. 03If node.val ≤ low or node.val ≥ high, return false.
  4. 04Recurse left with (low, node.val) and right with (node.val, high); both must pass.

Reference implementation

1
function isValidBST(root) {
2
  function valid(node, low, high) {
3
    if (!node) return true;
4
    if (node.val <= low || node.val >= high) return false;
5
    return valid(node.left,  low,      node.val)
6
        && valid(node.right, node.val, high);
7
  }
8
  return valid(root, -Infinity, Infinity);
9
}

Complexity

Time
O(n) — each node is visited once.
Space
O(h) for the recursion stack, where h is the tree height.