Validate Binary Search Tree
Given the root of a binary tree, determine whether it is a valid binary search tree: every node in a left subtree is strictly less than its ancestor, every node in a right subtree strictly greater, and all subtrees are themselves valid.
- 1 ≤ number of nodes ≤ 10^4
- -2^31 ≤ node value ≤ 2^31 - 1
- Comparing only with the direct parent is insufficient — the whole ancestor range matters
- Pass down (min, max) bounds
- Equivalently: in-order traversal must be strictly increasing
Nearly every tree problem is a traversal with the right information passed down (bounds, depth) or returned up (height, best path through this node). Inorder on a BST yields sorted order, which solves kth-smallest and validation; BFS with a queue yields levels.
Recurse with an allowed open interval (lo, hi), initially unbounded. A node is valid if its value lies strictly inside the interval and its left child is valid with (lo, value) while its right child is valid with (value, hi). Each subtree inherits the constraints of all ancestors, so a deep violation like the 3 under 5 is caught.
- Perform an in-order traversal and check that each value is strictly greater than the previous; identical cost and easy to do iteratively.