Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Balanced Binary Tree
Bookmark
Brute Force
Bottom-Up DFS
Iterative Stack
Input
Balanced (Example 1)
Unbalanced (Example 2)
Complete Tree (Balanced)
Custom
tree
=
[3, 9, 20, null, null, 15, 7]
3
9
20
15
7
scans
0
brute force: re-scan both subtrees at every node
3
9
20
15
7
scans
0
brute force: re-scan both subtrees at every node
3
9
20
15
7
scans
1
height(left) =
1
, scanned 1 node
3
9
20
15
7
scans
4
1 <= 1:
3
is balanced here
3
9
20
15
7
scans
4
height(right) =
0
, scanned 0 nodes
3
9
20
15
7
scans
4
check the balance at
20
3
9
20
15
7
h=1
h=1
scans
6
|
1
-
1
| =
0
<= 1
3
9
20
15
7
scans
6
height(left) =
0
, scanned 0 nodes
3
9
20
15
7
scans
6
0 <= 1:
15
is balanced here
3
9
20
15
7
scans
6
height(right) =
0
, scanned 0 nodes
3
9
20
15
7
scans
6
return true: tree is balanced
algo
master
.
io
Step:
Start: a tree is balanced if every node's subtree heights differ by at most 1
0 / 27
Input
Balanced (Example 1)
Unbalanced (Example 2)
Complete Tree (Balanced)
Custom
tree
=
[3, 9, 20, null, null, 15, 7]
0 / 27
algo
master
.
io
Step:
Start: a tree is balanced if every node's subtree heights differ by at most 1
