Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Validate Binary Search Tree
Bookmark
Check Ancestors
Range Validation
In-Order
Input
Valid BST (Simple)
Invalid BST (Example)
Invalid BST (Subtle)
Valid BST (Complex)
Custom
tree
=
[2, 1, 3]
2
1
3
isValidBST stack
scan each node's whole left and right subtree, then recurse
2
1
3
isValidBST stack
scan each node's whole left and right subtree, then recurse
2
root
1
3
isValidBST stack
2
allLessThan(2.left, 2)
1 < 2 ✓
1 < 2
✓
2
root
1
3
isValidBST stack
2
allGreaterThan(2.right, 2)
3 > 2 ✓
3 > 2
✓
2
1
root
3
isValidBST stack
2
1
isValidBST(
1
)
2
1
root
3
isValidBST stack
2
1
isValidBST(
1.left
)
2
1
3
isValidBST stack
2
1
∅
isValidBST(null):
return true
2
1
✓
3
root
isValidBST stack
2
3
isValidBST(
3
)
2
1
✓
3
root
isValidBST stack
2
3
isValidBST(
3.left
)
2
1
✓
3
isValidBST stack
2
3
∅
isValidBST(null):
return true
2
✓
1
✓
3
✓
isValidBST stack
return true
algo
master
.
io
Step:
Brute force: for every node, scan its whole left subtree for smaller values and its whole right subtree for larger values, then recurse
0 / 27
Input
Valid BST (Simple)
Invalid BST (Example)
Invalid BST (Subtle)
Valid BST (Complex)
Custom
tree
=
[2, 1, 3]
0 / 27
algo
master
.
io
Step:
Brute force: for every node, scan its whole left subtree for smaller values and its whole right subtree for larger values, then recurse
