Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Construct Quad Tree
Bookmark
Brute Force
Prefix Sum
Bottom-Up
Input
2x2 Mixed
8x8 Standard
4x4 Checkerboard
grid
=
2x2 grid
GRID
0
1
1
0
GRID
0
1
1
0
build(0,0,2)
GRID
0
1
1
0
DECISION
region
(0,0)
·
2×2
sum
…
/ total
4
build(0,0,2)
GRID
0
1
1
0
DECISION
region
(0,0)
·
2×2
sum
2
/ total
4
mixed → subdivide ▦
QUAD TREE
▦
build(0,0,2)
TL
build(0,0,1)
GRID
0
1
1
0
DECISION
region
(0,0)
·
1×1
sum
0
/ total
1
QUAD TREE
▦
build(0,0,2)
TR
build(0,1,1)
GRID
0
1
1
0
DECISION
region
(0,1)
·
1×1
sum
…
/ total
1
QUAD TREE
▦
0
build(0,0,2)
TR
build(0,1,1)
GRID
0
1
1
0
DECISION
region
(0,1)
·
1×1
sum
1
/ total
1
all 1s → leaf ●
QUAD TREE
▦
0
1
build(0,0,2)
BL
build(1,0,1)
GRID
0
1
1
0
DECISION
region
(1,0)
·
1×1
sum
1
/ total
1
QUAD TREE
▦
0
1
build(0,0,2)
GRID
0
1
1
0
DECISION
region
(1,0)
·
1×1
sum
1
/ total
1
all 1s → leaf ●
QUAD TREE
▦
0
1
1
build(0,0,2)
BR
build(1,1,1)
GRID
0
1
1
0
DECISION
region
(1,1)
·
1×1
sum
0
/ total
1
all 0s → leaf ○
QUAD TREE
▦
0
1
1
0
build(0,0,2)
GRID
0
1
1
0
QUAD TREE
▦
0
1
1
0
algo
master
.
io
Step:
Start: construct a quad tree from the 2×2 grid
0 / 22
Input
2x2 Mixed
8x8 Standard
4x4 Checkerboard
grid
=
2x2 grid
0 / 22
algo
master
.
io
Step:
Start: construct a quad tree from the 2×2 grid
