Validate a BST
MediumChecking a node against its direct children is not enough. Pass an allowed range down the tree and narrow it at each step.
boundsrecursion
TimeO(n)
SpaceO(h)
InputLevel order values
10
5
15
1
12
13
20
Every node must fit inside a window set by its ancestors, not just its parent.
1 / 7
valid(node, low, high):
if node is null: return true
if node.val <= low or node.val >= high: return false
return valid(node.left, low, node.val)
and valid(node.right, node.val, high)
Why it matters
The classic wrong answer passes this tree: 10 with left child 5 whose right child is 12.
Keyboard
space play← → stepr restartctrl K search
More in Binary Search Tree
Next visualiser
Heap: Push and Pop