Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Balance a Binary Search Tree
Bookmark
Sort + Rebuild
Inorder + D&C
Inorder Iterator
DSW In-Place
Input
Right-Skewed
Left-Skewed
Slightly Unbalanced
Custom
tree
=
[1, null, 2, null, 3, null, 4]
1
2
3
4
1 · flatten
height = 4
flatten to a sorted array, then rebuild balanced
1
2
3
4
1 · flatten
height = 4
flatten to a sorted array, then rebuild balanced
1
#1
2
#2
node
3
4
1 · flatten
height = 4
values
1
0
2
1
values +=
2
1
#1
2
#2
3
#3
node
4
1 · flatten
height = 4
values
1
0
2
1
3
2
inorder(
3
.left)
1
#1
2
#2
3
#3
4
#4
node
1 · flatten
height = 4
values
1
0
2
1
3
2
4
3
inorder(
4
.right)
2 · rebuild
height = 4
values
1
0
2
1
3
2
4
3
l
m
r
mid =
1
, values[mid] =
2
2
1
node
2 · rebuild
height = 4
values
1
0
2
1
3
2
4
3
build(0, -1)
: empty range
2
node
1
2 · rebuild
height = 4
values
1
0
2
1
3
2
4
3
l
m
r
node.right = build(
2, 3
)
2
1
3
node
2 · rebuild
height = 4
values
1
0
2
1
3
2
4
3
l
·m
r
node.right = build(
3, 3
)
2
1
3
4
node
2 · rebuild
height = 4
values
1
0
2
1
3
2
4
3
left > right:
return null
2
1
3
4
2 · rebuild
height 4 → 3
values
1
0
2
1
3
2
4
3
balanced: height 4 → 3
algo
master
.
io
Step:
Start: collect every value, sort it, then rebuild a balanced tree
0 / 59
Input
Right-Skewed
Left-Skewed
Slightly Unbalanced
Custom
tree
=
[1, null, 2, null, 3, null, 4]
0 / 59
algo
master
.
io
Step:
Start: collect every value, sort it, then rebuild a balanced tree
