LC 98 · Medium · Pre-order · pass bounds down
Validate Binary Search Tree
A property that a purely local check would get wrong, because ancestors constrain descendants.
Recognise it
Before any code, what in the question tells you this is the pattern?
A binary search tree, plus a property that is about more than a node and its immediate children. The giveaway is that a purely local check would pass on a tree you can see is wrong, which means information has to travel down from ancestors.
The brute force
Always have this one ready. It is the honest starting point, and it is what the real solution improves on.
At each node, check that the left child is smaller and the right child is larger, then recurse into both.
O(n) time.
This is not slow, it is wrong, and that makes it more instructive than a slow solution. Take the tree with root 5, left child 4, and a right child of that 4 equal to 6. Every parent-child pair passes: 4 is less than 5, and 6 is greater than 4. But 6 sits in the left subtree of 5 and is larger than 5, so the tree is not a BST. The check fails because being a BST is a statement about every ancestor, not just the nearest one.
The approach
The idea in plain language, before it becomes syntax.
Give each node a window of values it is allowed to hold. The root inherits an unbounded window. Whenever you move to a left child, the current node becomes a new ceiling, because everything to the left must be smaller than it. Moving right, the current node becomes a new floor.
A tree is a valid BST exactly when every node lies strictly inside the window it inherits. That single statement is provably equivalent to the definition, which is why this approach is correct where the local check is not: the window carries down the constraint from every ancestor, not just the parent.
There is a second correct approach worth knowing. An in-order traversal of a BST produces a strictly increasing sequence, so you can walk in order and check each value against the previous one. It uses less conceptual machinery but needs care with the very first node, and it does not generalise to pruning problems the way bounds do.
The algorithm
The same idea again, as steps you could follow with a pencil.
The solution
Now the code, and why each decision in it is the way it is.
def isValidBST(root):
def ok(node, low, high):
if not node:
return True
if not (low < node.val < high):
return False
# Going left caps the max; going right raises the min.
return ok(node.left, low, node.val) and ok(node.right, node.val, high)
return ok(root, float('-inf'), float('inf'))The comparison is strict on both ends. Under the usual definition duplicates make a tree invalid, so a single <code><=</code> flips the answer on a tree full of equal values.
Initial bounds must be genuinely unbounded. Using the smallest and largest machine integers breaks on a tree that actually contains those values, which is exactly the test case that gets written. Python uses infinities and the Java version uses nullable bounds, which is the cleanest way to say "no bound yet" in a language without them.
Bounds are passed down rather than results being passed up, which makes this a pre-order algorithm. That is the opposite direction of travel from the depth and path-sum problems, and noticing which direction information flows is a fast way to classify an unfamiliar tree question.
Where people slip
- Comparing each node only against its own children is wrong. A node deep in the left subtree can be larger than an ancestor while still being larger than its parent.
- The comparison is strict on both sides. Duplicate values make a tree invalid under the usual definition, so
<=anywhere is a bug. - Using integer sentinels for the initial bounds breaks when the tree contains those exact values. Use infinities, or nullable bounds as in the Java version.
Your notes
What tripped you up here? Write it in your own words.