Pattern Recognition Drill

#40 — Validate BST

Medium Trees

The Problem

Check if a binary tree is a valid binary search tree.

What approach would you use?

Think about it before scrolling down.

Key Signals

'Valid BST' → every node must satisfy: left < node < right GLOBALLY, not just locally
Pass tightening bounds (lo, hi) down the recursion

Tree Recursion

Recurse with (lo, hi) bounds. Left child tightens hi, right child tightens lo. O(n).

Alt: Stack

Inorder traversal should produce sorted order — check that each value > previous. O(n).

Common Trap

Checking only node.left.val < node.val < node.right.val is WRONG — misses non-local violations.

← #39 #41 →