Validate Binary Search Tree
Decide whether every node satisfies strict BST ordering.
Why does this pattern fit?
Restate the exact job
Decide whether every node satisfies strict BST ordering.
Each ancestor contributes a lower or upper bound, not just the parent.
O(n) time · O(h) stack
Checking only immediate children misses deep violations.
How to solve Validate Binary Search Tree
The goal is to solve this problem from the pattern, not to memorize a finished answer. Use this as a check after your own attempt.
What the question asks
Decide whether every node satisfies strict BST ordering.
Why Trees & recursive traversal fits
Each ancestor contributes a lower or upper bound, not just the parent.
State to maintain
A node with an allowed open interval.
Transition
Reject values outside bounds; recurse left with upper=value and right with lower=value.
Time and space
O(n) time · O(h) stack
Counterexample to the tempting mistake
Checking only immediate children misses deep violations.
Prove it again tomorrow
Close this page. Rebuild the state and transition from memory, write a test that exposes the mistake above, then solve a fresh input without looking back. A same-day reread is practice, not proof of retention.