Learn
Practice
Newsletter
Resources
Mobile
New
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Validate Binary Search Tree
1
isValidBST(Node(2))
Valid BST (Simple)
Invalid BST (Example)
Invalid BST (Subtle)
Valid BST (Complex)
Custom
tree
=
[2, 1, 3]
2
1
3
range
every node must fit in an open range (min, max)
2
1
3
range
every node must fit in an open range (min, max)
2
(-∞, +∞)
node
1
3
range
-∞
+∞
2
-∞ <
2
< +∞ ?
2
(-∞, +∞)
node
1
3
range
-∞
+∞
2
left range narrows to
(-∞, 2)
2
1
(-∞, 2)
node
3
range
-∞
2
1
-∞ <
1
< 2
✓
2
1
(-∞, 2)
node
3
range
-∞
2
1
right range narrows to
(1, 2)
2
1
✓
node
3
range
-∞
2
1
node
1
is valid:
return true
2
1
✓
3
(2, +∞)
node
range
2
+∞
3
2 <
3
< +∞ ?
∅
2
1
✓
3
range
node = null:
return true
∅
2
1
✓
3
range
node = null:
return true
2
✓
1
✓
3
✓
range
return true
Step:
Start: every node must lie in an open range (min, max); the root starts with (-Infinity, +Infinity)
0 / 24
Valid BST (Simple)
Invalid BST (Example)
Invalid BST (Subtle)
Valid BST (Complex)
Custom
tree
=
[2, 1, 3]
0 / 24
Step:
Start: every node must lie in an open range (min, max); the root starts with (-Infinity, +Infinity)
1
isValidBST(Node(2))
