The problem
Decide whether a binary tree is a valid binary search tree: for every node, all values in its left subtree are smaller and all values in its right subtree are larger.
Input: [5, 3, 8, 1, 6, 7, 9] Output: false (6 is in the left side of 5 but is bigger than 5)
Picture it
Picture every branch carrying a fence: a range of allowed values (low, high). The root may hold anything. Going left, the high end of the fence becomes the parent’s value; going right, the low end does. A node outside its fence breaks the rule, even if it looks fine next to its direct parent.
How to recognise it
- The input is a binary tree and the question is a yes/no check that every node must pass.
- The rule for a node depends on its ancestors, not only its parent ("all values in the left subtree"). That points to passing information down a depth-first search (DFS: follow one branch to the bottom before trying the next).
- Each step down narrows a range: going left caps the maximum, going right raises the minimum, so pass
(low, high)bounds as arguments. - Up to about 10^4 nodes, so each node should be visited a constant number of times.
Start with brute force
Follow the definition literally. For every node, collect every value in its left subtree and check they are all smaller, then collect the right subtree and check they are all larger. Then repeat for both children.
def values(node):
if not node:
return []
return values(node.left) + [node.val] + values(node.right)
def is_valid_bst_brute(root):
if not root:
return True
if any(v >= root.val for v in values(root.left)):
return False
if any(v <= root.val for v in values(root.right)):
return False
return is_valid_bst_brute(root.left) and is_valid_bst_brute(root.right)
It is correct, but each node is collected again for every ancestor: O(n log n) on a balanced tree, O(n²) on a chain (about 5 × 10^7 copies for 10^4 nodes). Space is O(n) for the lists.
From brute force to the idea
- Find the waste. The brute force collects whole subtrees only to learn the largest value on the left and the smallest on the right, and every ancestor re-checks the same nodes.
- Flip the direction. Instead of ancestors looking down, let each node carry down what its ancestors require: the range it must fall inside.
- Start wide open. The root may hold any value: its range is (−infinity, +infinity).
- Tighten on the way down. Going left, the upper bound becomes the parent's value; going right, the lower bound does. The other bound is inherited, which is how a grandparent's rule reaches a grandchild.
- Check once per node. If
lo < node.val < hifails, returnFalse. An empty child is always fine.
This is the key idea: pass (low, high) bounds down the tree and tighten them at each step.
The key idea
Pass (low, high) bounds down the tree and tighten them at each step. O(n).
Python solution
def is_valid_bst(root):
def check(node, lo, hi):
if not node:
return True
if not (lo < node.val < hi):
return False
return check(node.left, lo, node.val) and check(node.right, node.val, hi)
return check(root, -inf, inf)LeetCode adds the imports for you. To run this on your own machine, put this at the top: from math import inf
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n log n) balanced, O(n²) chain: subtrees are re-collected for every ancestor | O(n): the collected value lists |
| Bounds DFS (shown code) | O(n): each node is checked once with two comparisons | O(h): one call per level of the recursion, h is the tree height (n for a chain) |
Edge cases
- Empty tree (
rootisNone): returnsTrue. - Single node: returns
True. - Duplicate values (a 2 with a left child 2): returns
False, because the check is strict (<) and this problem forbids duplicates. - Grandchild breaks an ancestor's rule (
[5, 4, 6, null, null, 3, 7]): returnsFalse; the 3 is right of 5, and the inherited lower bound 5 catches it. - Extreme values (−2^31 or 2^31 − 1): returns
True, because the starting bounds are infinite, not integer limits. The code needsfrom math import inf. - Very deep tree: a chain of about 1,000 nodes hits Python's default recursion limit and raises
RecursionError. Raise the limit or use an explicit stack.
Common mistakes
- Comparing each node only with its own children. That accepts
[5, 4, 6, null, null, 3, 7], where 3 is less than 6 but sits to the right of 5. - Starting the bounds at the smallest and largest 32-bit integers, which wrongly rejects a node that holds exactly that value.
- Using
<=in the check, which accepts duplicates the problem forbids.
Some textbooks allow equal values, as long as they go left: every value in the left subtree is less than or equal to the node, and every value in the right subtree is strictly greater. Change the check for this rule. Describe your approach, then write it if you like.
Compare with our answer
Keep the same bounds DFS. Only the comparison changes: a node may now equal its upper bound (which came from an ancestor it sits to the left of), but must still be strictly greater than its lower bound.
from math import inf
def is_valid_bst_dup_left(root):
def check(node, lo, hi):
if not node:
return True
if not (lo < node.val <= hi):
return False
return check(node.left, lo, node.val) and check(node.right, node.val, hi)
return check(root, -inf, inf)
A 2 with a left child 2 is now valid; a 2 with a right child 2 is still invalid. Time O(n), space O(h).
A strong answer mentions: which side of the comparison becomes <= and why, that the bounds are passed down exactly as before, and a test with equal values on each side.
1. You must check that every node in a binary tree lies within 10 of every one of its ancestors. Which approach fits best?
The rule involves every ancestor, so carry a summary of them (their minimum and maximum) down the recursion, just like the BST bounds. Parent-only checks miss distant ancestors, and in-order sorting tests a different rule.
2. Why does the shown solution use O(h) extra space rather than O(n)?
A DFS keeps one stack frame per level of the current path, so the depth h decides the space. Python does not reuse frames for recursive calls (it has no tail-call optimisation), which is why a chain of n nodes needs n frames.
3. A learner starts the recursion with check(root, -2**31, 2**31 - 1). Which tree is now judged wrongly?
lo < node.val < hi is strict, so a value equal to the starting bound fails and the function returns False. Infinite starting bounds avoid this. The other trees are judged the same either way.
Score 60% or more and the lesson is marked complete.