BST Patterns

Validate BST

Pass an allowed range [min, max] down the tree. The root can be anything. Its left child must be < root (new max), its right child must be > root (new min). If any node violates its range, it's not a valid BST.

O(n)

O(h)

How It Works

Validating a BST means confirming every node satisfies constraints imposed by all of its ancestors, not merely its parent. The clean solution passes an allowed open interval (min, max) down the tree: the root gets (-infinity, +infinity); recursing left tightens the max to the current node's value; recursing right raises the min. A node fails if its value falls outside its inherited range. This is a textbook top-down parameter-passing pattern.

The classic mistake — checking only that each node beats its immediate children — misses violations like a right-subtree node smaller than the grandparent, which the range method catches automatically. An equivalent approach runs an in-order traversal and verifies the sequence is strictly increasing, since only true BSTs produce sorted in-order output. Both visit each node once: O(n) time, O(h) recursion space.

Step-by-Step Visualization

Validate BST with range checking

5range (-∞, ∞) ✓

1/3

Code

Java

static boolean isValidBST(TreeNode root) {
  return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

static boolean isValidBST(TreeNode root, long min, long max) {
  if (root == null) return true;
  if (root.val <= min || root.val >= max) return false;

  return isValidBST(root.left, min, root.val) &&
         isValidBST(root.right, root.val, max);
}

Tips & Gotchas

1Pass min/max bounds down the recursion

2Left child must be less than parent, right must be greater

3In-order traversal should yield strictly increasing sequence

Practice Problems

1Validate Binary Search Tree
2Recover Binary Search Tree
3Kth Smallest Element in a BST
4Convert Sorted Array to Binary Search Tree

About the BST Patterns Pattern

Binary Search Trees guarantee: everything in the left subtree < root < everything in the right subtree. This property lets you make decisions at each node about which direction to go, effectively doing binary search on a tree.

Key insight

Tree problems are almost always DFS (recursion) or BFS (level-order). The pattern: solve for children, combine results, return up. BST's sorted property lets you prune half the tree.

Common Trees Interview Problems

Maximum Depth of Binary Tree
Validate BST
Binary Tree Level Order Traversal
Lowest Common Ancestor
Serialize and Deserialize Binary Tree
Diameter of Binary Tree

Frequently Asked Questions

Why is comparing each node only with its direct children insufficient?

The BST property is transitive across the whole ancestor chain: every node in a left subtree must be smaller than every ancestor it descends left from. A tree can pass all local parent-child checks while a deep node still violates a grandparent's bound, and only inherited ranges or an in-order check catch it.

Range-passing versus in-order checking — which should I use?

Both are O(n) time and O(h) space, so it is largely style. Range-passing can fail fast anywhere in the tree and adapts naturally to variants like counting valid subtrees; the in-order check is shorter to write and reuses a traversal you likely already know. Watch duplicates: strict inequalities matter in both.

How do I handle node values at the extremes of the integer range?

Using integer sentinels like INT_MIN and INT_MAX breaks when a node holds those exact values. Use nullable bounds (null meaning unbounded), a wider type such as long, or the in-order previous-node comparison, which needs no sentinels at all.