Validate Binary Search Tree
The problem
Decide whether every node in a binary tree obeys strict BST ordering: all values in its left subtree are smaller, and all in its right subtree are larger.
Example
Root 8, right child 12, and 12’s left child 6 → false.
Need a hint?
Checking only immediate children misses violations inherited from ancestors.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Traverse with exclusive lower and upper bounds. Reject a value outside its allowed range. For a left child, tighten the upper bound to the current value; for a right child, tighten the lower bound. Null subtrees are valid. Duplicate values fail strict ordering.
Complexity
O(n) time and O(h) stack space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.