Trees crash course ↗ · 140

98. Validate Binary Search Tree

A binary tree is a BST when every node fits the strict ordering of all its ancestors, not just its parent. Carry an open (low, high) interval down each path and check every node against it.

● MediumDFSValid BST BoundsTypeScript

PROBLEM What we're solving

Given a binary tree, return true iff it is a valid binary search tree: for every node, all values in its left subtree are strictly less and all values in its right subtree are strictly greater. [2,1,3] → true. The tree [5,1,4,null,null,3,6] → false: node 3 sits in the right subtree of 5, so it must exceed 5, but it doesn't.

KEY IDEA Each node owns an open (low, high) interval

Insight → a node is valid iff its value lies strictly inside the interval (low, high) inherited from its ancestors. The root starts with (−∞, +∞). Going left tightens the upper bound to the parent's value; going right raises the lower bound to it. Thread those bounds down with DFS and every node validates itself in O(1).

RECIPE Descend with bounds, tighten as you go

0 · Base case. A null subtree is a valid BST → return true.
1 · Range check. If node.val <= low or node.val >= high, it breaks an ancestor's ordering → return false. Use strict bounds so duplicates fail.
2 · Recurse left. Everything left must stay below node.val: call dfs(left, low, node.val) — high tightens.
3 · Recurse right. Everything right must exceed node.val: call dfs(right, node.val, high) — low tightens.
4 · Combine. The tree is valid iff this node is in range AND both subtrees report valid.

Classic confusion → it is not enough to check each node only against its parent. In [5,1,4,null,null,3,6] the node 3 is a valid left child of 4 (3 < 4), yet the tree is invalid because 3 lives in 5's right subtree and must be greater than 5. Only the inherited (low, high) interval — not the immediate parent — catches this.

COST Complexity & alternatives

Check every pair / re-scan subtrees

O(n²)

Validating each node against all descendants repeats work.

DFS with (low, high) bounds

O(n)

Visit each node once; O(h) recursion stack.

Space note

Time is O(n) — one visit per node. Space is O(h) for the recursion stack, where h is the tree height: O(log n) when balanced, O(n) in the worst case (a degenerate chain).

Pattern transfer → the same range-threading DFS validates other ordered structures, and the in-order traversalalternative (a BST's in-order sequence is strictly increasing) powers Kth Smallest Element in a BST and Recover Binary Search Tree.

RUN IT Thread tightening (low, high) bounds down the tree

tree =

step 0 / 7

STARTStart isValidBST. Call dfs(root, -Infinity, Infinity) — root has no ancestor constraints.

1// LeetCode 98 — Validate Binary Search Tree
2class TreeNode {
3  val: number;
4  left: TreeNode | null;
5  right: TreeNode | null;
6  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
7    this.val = val;
8    this.left = left;
9    this.right = right;
10  }
11}
12 
13function isValidBST(root: TreeNode | null): boolean {
14  // Each node carries an OPEN interval (low, high) it must fall strictly inside.
15  const dfs = (
16    node: TreeNode | null,
17    low: number,   // exclusive lower bound, -Infinity at root
18    high: number,  // exclusive upper bound, +Infinity at root
19  ): boolean => {
20    if (node === null) return true;          // empty subtree is valid
21    if (node.val <= low || node.val >= high) // must be strictly within bounds
22      return false;
23    // Tighten the bound as we descend: left shrinks high, right raises low.
24    return (
25      dfs(node.left, low, node.val) &&
26      dfs(node.right, node.val, high)
27    );
28  };
29 
30▶  return dfs(root, -Infinity, Infinity);
31}

State

null

node

-inf

low (>)

+inf

high (<)

in bounds?

(empty)

call stack

current nodeinherited boundsrecursion call stackin bounds / validviolation

slowfast

TYPESCRIPT The solution, annotated

isValidBST.ts
// LeetCode 98 — Validate Binary Search Tree
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function isValidBST(root: TreeNode | null): boolean {
  // Each node carries an OPEN interval (low, high) it must fall strictly inside.
  const dfs = (
    node: TreeNode | null,
    low: number,   // exclusive lower bound, -Infinity at root
    high: number,  // exclusive upper bound, +Infinity at root
  ): boolean => {
    if (node === null) return true;          // empty subtree is valid
    if (node.val <= low || node.val >= high) // must be strictly within bounds
      return false;
    // Tighten the bound as we descend: left shrinks high, right raises low.
    return (
      dfs(node.left, low, node.val) &&
      dfs(node.right, node.val, high)
    );
  };

  return dfs(root, -Infinity, Infinity);
}

Reading it block by block

The helper signature. dfs(node, low, high)asks: "is the subtree rooted here a valid BST whose every value falls strictly between low and high?" The bounds are exclusive.

Base case. A null node represents an empty subtree, which is trivially a valid BST → return true.

Range check. node.val <= low || node.val >= high fails the node. Using <= / >= (not < / >) rejects duplicate values, which a strict BST forbids.

Tighten and recurse. Left subtree inherits (low, node.val) — the parent becomes the new ceiling. Right subtree inherits (node.val, high)— the parent becomes the new floor. This is exactly what propagates the "greater than every left-ancestor, less than every right-ancestor" constraint.

Kick-off. The root has no constraints, so we call dfs(root, -Infinity, Infinity). Using ±Infinity avoids special-casing the root or worrying about Number.MIN_SAFE_INTEGER edge values.

Complexity → O(n) time — each node is visited exactly once. O(h) space for the recursion stack: O(log n) balanced, O(n) worst case (skewed tree).

INTERVIEWFollow-ups they'll ask

"Do it without bounds?"Do an in-order traversal and verify each value is strictly greater than the previous one — a BST's in-order sequence is strictly increasing.
"Iterative version?" Replace recursion with an explicit stack of [node, low, high] triples, or an iterative in-order walk tracking the previous value.
"Why ±Infinity instead of integer limits?" It cleanly handles nodes equal to Number.MIN_SAFE_INTEGER / MAX_SAFE_INTEGER without false failures.
"Allow duplicates?" Decide a convention (e.g. duplicates go right) and relax one comparison to < / >= accordingly.
"Recover a BST with two swapped nodes?" Use the in-order approach to find the two out-of-order elements and swap them back.

OPTIMAL DFS

isValidBST.ts
// LeetCode 98 — Validate Binary Search Tree
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function isValidBST(root: TreeNode | null): boolean {
  // Each node carries an OPEN interval (low, high) it must fall strictly inside.
  const dfs = (
    node: TreeNode | null,
    low: number,   // exclusive lower bound, -Infinity at root
    high: number,  // exclusive upper bound, +Infinity at root
  ): boolean => {
    if (node === null) return true;          // empty subtree is valid
    if (node.val <= low || node.val >= high) // must be strictly within bounds
      return false;
    // Tighten the bound as we descend: left shrinks high, right raises low.
    return (
      dfs(node.left, low, node.val) &&
      dfs(node.right, node.val, high)
    );
  };

  return dfs(root, -Infinity, Infinity);
}

Complexity → O(n) time — each node is visited exactly once. O(h) space for the recursion stack: O(log n) balanced, O(n) worst case (skewed tree).

ALT 1 Brute force — check every node against its whole subtrees

O(n²) time · O(n) space

For each node, verify the BST property directly: every value in its left subtree must be smaller and everyvalue in its right subtree larger — then recurse into both children.

approach-2.ts
function isValidBST(root: TreeNode | null): boolean {
  // Collect all values in a subtree.
  function values(node: TreeNode | null): number[] {
    if (node === null) return [];
    return [node.val, ...values(node.left), ...values(node.right)];
  }

  function valid(node: TreeNode | null): boolean {
    if (node === null) return true;
    // Whole left subtree strictly below, whole right subtree strictly above.
    for (const v of values(node.left)) {
      if (v >= node.val) return false;
    }
    for (const v of values(node.right)) {
      if (v <= node.val) return false;
    }
    return valid(node.left) && valid(node.right);
  }

  return valid(root);
}

Note → Correct, but it re-walks entire subtrees at every node, so a skewed tree of n nodes costs O(n²). The bounds-passing DFS instead threads an open(low, high) interval down the recursion, validating each node inO(1) for an overall O(n) single pass.

MNEMONIC The one-liner

"Each node lives in an open (low, high) box — left shrinks the ceiling, right raises the floor."

TRIGGERS When you see _ → reach for _

"is this tree a valid BST?"	DFS carrying (low, high) bounds
child looks fine vs parent but tree invalid	inherited ancestor bounds, not parent
going left in a BST	tighten high to node.val
going right in a BST	raise low to node.val

SKELETON The reusable shape

skeleton.ts
function isValidBST(root: TreeNode | null): boolean {
  const dfs = (node: TreeNode | null, low: number, high: number): boolean => {
    if (!node) return true;
    if (node.val <= low || node.val >= high) return false;
    return dfs(node.left, low, node.val)
        && dfs(node.right, node.val, high);
  };
  return dfs(root, -Infinity, Infinity);
}

FLASHCARDS Tap to flip

What interval does each node have to satisfy?

The open (low, high) inherited from its ancestors: low < node.val < high.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What makes the bounds approach correct where "compare each node to its parent" fails?

QUESTION 02

When recursing into the LEFT child, the bounds become:

QUESTION 03

For the tree [5,1,4,null,null,3,6], the function returns:

QUESTION 04

Why use strict comparisons (< and >) rather than <= and >=?

QUESTION 05

Why initialize the root call with -Infinity and +Infinity?

QUESTION 06

Time and space complexity of the bounds DFS?

QUESTION 07

Which alternative also validates a BST without explicit bounds?

QUESTION 08

#98 · Validate Binary Search TreeA binary tree is a BST when every node fits the strict ordering of all its ancestors, not just its parent. Thread an open (low, high) interval down each DFS path and check every node against it.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Each node owns an open (low, high) interval

RECIPE Descend with bounds, tighten as you go

COST Complexity & alternatives

Space note

RUN IT Thread tightening (low, high) bounds down the tree

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL DFS

ALT 1 Brute force — check every node against its whole subtrees

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _