21. Validate Binary Search Tree

Difficulty:MediumPattern:Tree DFS Range BoundingTime:O(n)Space:O(h)

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

How It Works & Algorithmic Design

Solves using Recursive Range Bound Validation:

BST Definition: For every node, all nodes in its left subtree must be strictly smaller (val < node.val), and all nodes in its right subtree must be strictly larger (val > node.val).
Range Propagation: Pass valid bounds (min, max) down recursive calls:
- Base Case: if (node === null) return true.
- Violation: if (min !== null && node.val <= min) || (max !== null && node.val >= max) return false.
- Recurse Left: validate(node.left, min, node.val).
- Recurse Right: validate(node.right, node.val, max).

Why This Approach Works Best

Validating global bounds (min, max) prevents invalid BST topologies where deep right sub-nodes violate ancestor limits.

Example Walkthrough

Input: [5, 1, 4, null, null, 3, 6]

Invalid BST.

Violation: Node 3 is in right subtree of 5, but 3 < 5.

Range check fails.

Output: false

Not a valid BST.

Answer: Validate BST using range limits

function isValidBST(root, min = null, max = null) {
  if (!root) return true;
  if ((min !== null && root.val <= min) || (max !== null && root.val >= max)) return false;
  return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
}

💡 Propagate min and max bounds recursively to ensure strict BST order invariants.

Key Takeaways

Checking local children alone is insufficient; ancestor bounds must be propagated.
Inorder traversal of a BST produces a strictly increasing sorted sequence.
Runs in $O(n)$ time and $O(h)$ space.