Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
A BST is valid only if EVERY node satisfies the global ordering — not just its immediate parent. The interview-grade answer is a DFS that passes down a (low, high) open interval: each node must be strictly inside its bounds, then recurse left with high = node.val and right with low = node.val. The elegant alternative is an inorder traversal, which must produce a strictly increasing sequence. Both are O(n) time, O(h) space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you understand that the BST property is global. Many candidates write a check that only compares a node to its immediate children and pass the trivial cases while failing on deeper violations.
Where candidates slip
Comparing only node.val against node.left.val and node.right.val (local check), and forgetting integer overflow when seeding bounds with Integer.MIN/MAX_VALUE.
How to stand out
State the global-vs-local insight explicitly, handle the overflow with Long or null bounds, and offer the inorder-is-strictly-increasing alternative as a second solution.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewIs this tree a valid BST?Compare each node to whom?Only its parentAll ancestorsExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 3
Local-Only Check (Brute / Wrong — Name to Reject)
1Hint 1Explore hintHide hint
The naïve reading is: each node just needs its left child smaller and right child larger. Why might that not be enough?
2Hint 2Explore hintHide hint
Construct [5,4,6,null,null,3,7]: every parent-child pair looks valid, yet 3 sits in 5's right subtree where everything must exceed 5.
3Hint 3Explore hintHide hint
The fix is to remember not just the parent but the tightest lower and upper bound inherited from ALL ancestors.
A · Core idea
The instinctive solution checks, at each node, only that node.left.val < node.val < node.right.val. It runs in linear time and passes shallow examples, which is exactly why it's dangerous.
Why it's wrong. The BST property says the entire left subtree is smaller and the entire right subtree is larger — a transitive, global constraint. A grandchild can satisfy its parent yet violate a grandparent. In [5,4,6,null,null,3,7], node 3 is the left child of 6 (so 3 < 6 passes the local test), but 6 is in 5's right subtree, meaning every node under 6 — including 3 — must be greater than 5. A local check never sees the bound inherited from 5, so it wrongly returns true.
The lesson. The only safe information to carry is the interval (low, high) accumulated from every ancestor on the path down. Mentioning this broken approach and immediately refuting it with the counterexample is a strong signal you understand the problem's actual difficulty.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [5,4,6,null,null,3,7]node 5
4 < 5 < 6 → looks OK locally
passes (but shouldn't trust this yet)Local check says true; correct answer is false.C · Code with teaching comments
Reference implementation preview// BROKEN — do not ship. Compares only against immediate children. public boolean isValidBSTLocal(TreeNode node) { if (node == null) return true; if (node.left != null && node.left.val >= node.val) return false; if (node.right != null && node.right.val <= node.val) return false;Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proofHide the proof
The bug is conceptual, not syntactic — the code is clean and fast, it's just answering the wrong question. Interviewers plant exactly this trap, so the move that scores points is naming it before you fall into it.
ComplexityO(n) time, O(h) space — It still visits every node once (O(n)) with O(h) recursion depth, but correctness — not complexity — is the problem: it accepts invalid trees.
E · Edge cases and pitfalls3Believing this is correct because it passes [2,1,3] and other shallow trees.Explore edge casesHide edge cases
Pitfalls
- Believing this is correct because it passes [2,1,3] and other shallow trees.
- Not testing against a deep-violation case like [5,4,6,null,null,3,7].
- Shipping it because it's O(n) — speed is irrelevant when the answer is wrong.
Approach 2 of 3 · Optimal
Bounds-Propagating DFS (Optimal)
1Hint 1Explore hintHide hint
What if every node knew the tightest lower and upper value it's allowed to take, based on the turns taken from the root?
2Hint 2Explore hintHide hint
Going LEFT tightens the upper bound to the parent's value; going RIGHT tightens the lower bound to the parent's value. Seed the root with (-∞, +∞).
3Hint 3Explore hintHide hint
At each node assert low < node.val < high. If it holds, recurse left with (low, node.val) and right with (node.val, high). Use Long or null sentinels to dodge integer overflow at the limits.
A · Core idea
Thread an open interval (low, high) through the recursion that captures the constraint inherited from every ancestor on the path to the current node. A node is valid iff low < node.val < high.
How the interval evolves. Start the root with (-∞, +∞) — it may be any value. When you descend into the left child, that whole subtree must be less than the current node, so the upper bound tightens to node.val: recurse with (low, node.val). When you descend into the right child, everything must exceed the current node, so the lower bound tightens to node.val: recurse with (node.val, high). The bounds only ever get narrower as you go deeper, which is precisely how the global constraint is enforced locally.
Why this fixes the trap. Re-run [5,4,6,null,null,3,7]. Root 5 has bounds (-∞,+∞). Going right to 6 gives bounds (5, +∞). Going left from 6 to 3 gives bounds (5, 6). Now 3 is checked against 5 < 3 < 6, which is false — caught immediately. The bound 5 survived two levels down because we carried it, which the local check never did.
The overflow detail. Node values can be exactly Integer.MIN_VALUE or MAX_VALUE. If you seed bounds with those same ints and compare with strict <, a legitimate extreme value gets rejected, or arithmetic on the bound overflows. The clean fixes are to type the bounds as Long (Long.MIN_VALUE/MAX_VALUE) or to use null to mean 'no bound yet' and skip the comparison when a bound is null. Mention this proactively — it's the detail that separates a correct answer from one that fails a hidden test.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [5,1,4,null,null,3,6]How to read it:Each edge label is the interval handed to the child. Node 4 receives (5,+∞) and fails because 4 < 5.
falseC · Code with teaching comments
D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proofHide the proof
The mental model is a shrinking window. Every left turn lowers the ceiling, every right turn raises the floor, and the window can only narrow. A node is valid exactly when it lands strictly inside the window it inherited — that single sentence is the whole algorithm.
ComplexityO(n) time, O(h) space — Each node is checked once against its O(1) bounds → O(n) time. Recursion depth equals the height h → O(h) space, which is O(log n) for a balanced tree and O(n) worst case for a skewed tree.
E · Edge cases and pitfalls6root = [Integer.MIN_VALUE] (= -2147483648) — With Long/inf bounds it passes; with Integer.MIN_VALUE seeds and a <= check it would wrongly fail. This is the overflow test.Explore edge casesHide edge cases
Edge cases handled
root = [Integer.MIN_VALUE] (= -2147483648)With Long/inf bounds it passes; with Integer.MIN_VALUE seeds and a <= check it would wrongly fail. This is the overflow test.root = [2,2,2]Duplicate values violate strict ordering — 2 is not < 2, so it returns false.root = [1] (single node)-inf < 1 < +inf → returns true.
Pitfalls
- Seeding with Integer.MIN_VALUE/MAX_VALUE — breaks on nodes holding those exact values.
- Using <= / >= where strict < / > is required (or vice versa) — flips the duplicate-handling behaviour.
- Swapping which bound tightens on left vs right — a very common copy-paste slip.
Approach 3 of 3
Inorder Traversal — Strictly Increasing (Alternative)
1Hint 1Explore hintHide hint
Recall what an inorder traversal of a BST produces. If the tree is valid, what property must that output sequence have?
2Hint 2Explore hintHide hint
Inorder of a valid BST is strictly increasing. So do an inorder walk and compare each value to the previous one.
3Hint 3Explore hintHide hint
Keep a single `prev` variable. The instant you see prev >= current, the tree is invalid — you can bail early without finishing the walk.
A · Core idea
This approach leans on the defining property of BSTs: an inorder traversal visits values in sorted order if and only if the tree is a valid BST. So instead of reasoning about bounds, just walk the tree inorder and confirm the output is strictly increasing.
The mechanism. Carry a single prev value (initially negative infinity / null). Each time the inorder walk reaches a node, compare node.val with prev. If node.val <= prev, the sequence isn't strictly increasing, so the tree is invalid — return false immediately. Otherwise update prev = node.val and continue. Because we only ever look at adjacent elements of the inorder sequence, one scalar of state is enough; we don't materialize the whole sorted list.
Why it's equivalent to the bounds version. Both enforce the global ordering — the bounds version does it spatially (an interval per node) while the inorder version does it temporally (the just-visited value is the strictest lower bound for the next value). They have identical O(n)/O(h) cost; pick whichever you can write more confidently. The inorder framing also generalizes beautifully: stop at the kth node for Kth Smallest, or record the two out-of-order nodes for Recover Binary Search Tree.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [5,1,4,null,null,3,6]visit 1
1 > -∞ → ok, prev = 1
valid so farfalseC · Code with teaching comments
Reference implementation previewprivate TreeNode prev; public boolean isValidBST(TreeNode root) { prev = null; return inorder(root);Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proofHide the proof
If you remember exactly one fact about BSTs for interviews, make it 'inorder traversal yields sorted order'. It turns Validate BST, Kth Smallest, BST Iterator, and Recover BST all into variations on a single inorder walk.
ComplexityO(n) time, O(h) space — A single inorder pass touches every node once → O(n). Done recursively the call stack is O(h); the iterative-stack version is also O(h). You only store one previous value, so no extra O(n) buffer is needed.
E · Edge cases and pitfalls6root = [1,1] — Inorder yields 1,1 — not strictly increasing, so returns false (duplicates rejected).Explore edge casesHide edge cases
Edge cases handled
root = [1,1]Inorder yields 1,1 — not strictly increasing, so returns false (duplicates rejected).root = [3,1,5,0,2,4,6]Inorder = 0,1,2,3,4,5,6 — strictly increasing → true.root = [Integer.MIN_VALUE, null, Integer.MAX_VALUE]Using a null/-inf prev avoids overflow; sequence MIN, MAX is increasing → true.
Pitfalls
- Initializing prev to Integer.MIN_VALUE — a node equal to MIN_VALUE then fails the >= test incorrectly; use null or -inf.
- Using >= vs > inconsistently with the duplicate rule.
- Collecting the full inorder list then checking sortedness — works but wastes O(n) memory; one prev variable suffices.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Local comparison instead of inherited bounds
Checking node.val only against its immediate children passes [5,4,6,null,null,3,7] even though 3 violates the ancestor bound from 5. Validity is global.
Explore the code comparisonHide the code comparison
Local comparison instead of inherited bounds
Checking node.val only against its immediate children passes [5,4,6,null,null,3,7] even though 3 violates the ancestor bound from 5. Validity is global.
Don't write this
def isValidBST(self, node):
if not node:
return True
if node.left and node.left.val >= node.val:
return False
if node.right and node.right.val <= node.val:
return False
return self.isValidBST(node.left) and self.isValidBST(node.right)Write this instead
def isValidBST(self, root):
def validate(node, low, high):
if not node:
return True
if not (low < node.val < high):
return False
return (validate(node.left, low, node.val)
and validate(node.right, node.val, high))
return validate(root, float('-inf'), float('inf'))2Integer overflow on the seed bounds
Seeding with Integer.MIN_VALUE/MAX_VALUE breaks when a node holds exactly that value, because the strict comparison then rejects a legitimate node. Use Long or null.
Explore the code comparisonHide the code comparison
Integer overflow on the seed bounds
Seeding with Integer.MIN_VALUE/MAX_VALUE breaks when a node holds exactly that value, because the strict comparison then rejects a legitimate node. Use Long or null.
Don't write this
private boolean validate(TreeNode node, int low, int high) {
if (node == null) return true;
if (node.val <= low || node.val >= high) return false; // overflow at int limits
return validate(node.left, low, node.val)
&& validate(node.right, node.val, high);
}Write this instead
private boolean validate(TreeNode node, long low, long high) {
if (node == null) return true;
if (node.val <= low || node.val >= high) return false;
return validate(node.left, low, node.val)
&& validate(node.right, node.val, high);
}3Wrong strictness lets duplicates through
BSTs here forbid equal keys. Using < where the bound check should reject equality (or vice versa) silently accepts an invalid duplicate.
Explore the code comparisonHide the code comparison
Wrong strictness lets duplicates through
BSTs here forbid equal keys. Using < where the bound check should reject equality (or vice versa) silently accepts an invalid duplicate.
Don't write this
if (node.val < low || node.val > high) return false; // allows node.val == boundWrite this instead
if (node.val <= low || node.val >= high) return false; // strictly inside onlyRevise
Carry the pattern into the interview
Pattern to remember
Bounds-propagating DFS (min/max interval) — or strictly-increasing inorder
Code pattern to memorize
valid(node, low, high):
if node is null: return True
if not (low < node.val < high): return False
return valid(node.left, low, node.val)
and valid(node.right, node.val, high)Rules to remember
- 1Validity is global, not local — a node must beat every ancestor, not just its parent. This is THE trap of the problem.
- 2Comparisons are strict (
<, not≤) — BSTs here forbid duplicate values across the ordering. - 3Pass the bound open interval down: recurse left with
high = node.val, recurse right withlow = node.val. - 4Seed the root with
(-∞, +∞). UseLong.MIN_VALUE/MAX_VALUEornullsentinels to surviveInteger.MIN/MAX_VALUEnode values. - 5Inorder alternative: a valid BST's inorder traversal is strictly increasing — track the previous value and fail on
prev >= curr.
Use this pattern when
- You must verify a tree obeys the BST ordering invariant everywhere
- Any 'is this tree a valid X?' where the constraint propagates from ancestors to descendants
- You can exploit that inorder of a BST is sorted (validate, kth-smallest, fix-swapped-nodes)
Choose another pattern when
- You only compare each node to its direct parent → that's the buggy 'local check' that fails [5,4,6,null,null,3,7]
- The tree isn't a BST at all → ordering reasoning doesn't apply
- You need the values themselves sorted, not a yes/no → just do an inorder traversal
Interview takeaway
The whole problem is a trap about the word 'every'. Once you realize each node is constrained by an interval inherited from all its ancestors — not just its parent — the bounds-DFS writes itself. The inorder-is-sorted view is the same idea from a different angle and is worth knowing for the whole BST family.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternBounds-propagating DFS enforces a global invariant by carrying ancestor information down the recursion as a shrinking interval. The inorder-is-sorted view is the BST-specific twin. This pair of ideas underpins the entire BST family: Kth Smallest, Recover BST, LCA of a BST, and BST iterators.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Kth Smallest Element in a BSTInorder traversal is sorted — return the kth value emitted, stopping early.
- Recover Binary Search TreeComing soonInorder finds the two nodes that are out of strictly-increasing order; swap their values.
- Lowest Common Ancestor of a BSTUse the BST ordering to decide which subtree to descend — no full search needed.
- Search in a Binary Search TreeComing soonThe same ordering invariant lets you binary-search the tree in O(h).