Given the root of a binary tree, return whether it is a valid binary search tree: every key in a node's left subtree is strictly smaller, and every key in its right subtree strictly larger.
Before you code
Checking each node only against its own children is the classic bug. In the third example, 3 is a correct left child of 6, but it sits in 5's right subtree and is smaller than 5.
Hints
- Pass down an allowed open range
(low, high). The root's range is unbounded. - A left child inherits
(low, node.val); a right child inherits(node.val, high). - Alternative: an inorder traversal of a valid BST is strictly increasing. Track the previous value as you go.
Production & complexity notes
When solving Validate binary search tree on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Binary search trees to reinforce the underlying pattern.
What it practices
The search tree property over whole subtrees, from Binary search trees.