dsa.university
start_free
Blog/TREES

Why your BST validation passes the samples and dies on depth

A local check is never a tree invariant. The classic validate-BST bug, why every shallow test misses it, and why the two standard fixes are secretly the same fix.

LH
Dr. Lena HoffCurriculum lead
18 August 2026·7 min read

Almost everyone writes the same first attempt at validating a binary search tree, and almost everyone's first attempt passes every test they can think up by hand. That is what makes it worth writing about: the bug is not in the code you can see, it is in the definition you thought you were implementing.

The attempt

python
1def isValid(node):
2 if not node:
3 return True
4 if node.left and node.left.val >= node.val:
5 return False
6 if node.right and node.right.val <= node.val:
7 return False
8 return isValid(node.left) and isValid(node.right)

Read it out loud and it sounds exactly like the definition: left is smaller, right is bigger, check every node. Draw a three-node tree and it is correct. Draw a seven-node tree and it is still correct. It will pass any example small enough to fit on a whiteboard.

The counterexample

Consider a root of 10, a left child of 5, and give that 5 a right child of 12. Every parent-child pair is fine: 5 is less than 10, and 12 is greater than 5. But 12 sits in the left subtree of 10, and everything in that subtree must be under 10. The tree is invalid and the code says it is fine.

The actual bug

The BST property constrains subtrees, not children. A node bounds an entire region of the tree, and a check that only looks one level down can never see that.

Fix one: carry the range down

Instead of comparing to the parent, pass the legal interval down. The root may be anything. A left child inherits its parent's lower bound and gains the parent's value as a new upper bound. The right child mirrors it.

python
1def isValid(node, low=float('-inf'), high=float('inf')):
2 if not node:
3 return True
4 if not (low < node.val < high):
5 return False
6 return (isValid(node.left, low, node.val)
7 and isValid(node.right, node.val, high))

Now the 12 arrives carrying the interval (5, 10) and fails immediately, three levels from where the mistake was made. That is the whole point: the constraint travelled.

Fix two: walk it inorder

An inorder traversal of a valid BST is sorted. So walk the tree inorder and check that each value beats the previous one. No bounds, no extra parameters.

python
1def isValid(root):
2 prev = float('-inf')
3 stack, node = [], root
4 while stack or node:
5 while node:
6 stack.append(node)
7 node = node.left
8 node = stack.pop()
9 if node.val <= prev:
10 return False
11 prev = node.val
12 node = node.right
13 return True

They are the same idea

The inorder version is the bounds version unrolled. When you visit a node inorder, every ancestor constraint has already been applied by the order of the walk — the previous value is exactly the tightest lower bound in force. One version carries the constraint explicitly; the other lets the traversal order carry it.

  • →Prefer bounds if you want an early exit and O(h) space.
  • →Prefer inorder if you are already walking the tree for another reason.
  • →If you keep the previous value in a plain variable, seed it with negative infinity, not None — otherwise the first comparison silently short-circuits.

The transferable lesson

Any time your recursion only inspects a node and its immediate children, stop and ask what an ancestor three levels up could still ruin. This shape recurs constantly: interval merging, range trees, segment trees, and validity checks on any structure where a node governs a region rather than a neighbour.

bstrecursioninvariants
Practise this

Reading about a pattern is not the same as producing it under time pressure. The problems that drill this are in the curriculum, in order.

open_curriculumcreate_account
next The sliding window invariant you should write down before you code

Related reading.

PATTERNS

The sliding window invariant you should write down before you code

8 min readFUNDAMENTALS

Reading a call stack without a debugger

7 min readFUNDAMENTALS

Recursion to iteration, without breaking the base case

7 min read