Construct Quad Tree
Core idea: A square region is a single leaf if every cell in it is the same value; otherwise cut it into four equal quadrants and recurse on each — the recursion is the spatial subdivision.
Problem, rephrased
You're building a black-and-white image format. The image is an n × n pixel grid where every pixel is 0 (white) or 1 (black), and n is always a power of two (1, 2, 4, 8, …). Storing every pixel is wasteful when big areas are a solid color, so you compress the image into a quad tree:
- Look at the whole square. If all its pixels are the same value, store it as a single leaf that remembers that one value. Done — no children.
- Otherwise the square is mixed, so chop it into four equal sub-squares —
topLeft,topRight,bottomLeft,bottomRight— and compress each of those the same way. The square becomes an internal node with four children.
Each node has these fields:
val—True/False(i.e.1/0); only meaningful on a leaf.isLeaf—Trueif this node represents a uniform region.topLeft,topRight,bottomLeft,bottomRight— the four children (allNoneon a leaf).
Return the root node of the quad tree.
| Input grid | Quad tree it produces |
|---|---|
[[1]] |
one leaf, val=1 |
[[1,1],[1,1]] |
one leaf, val=1 (whole 2×2 is uniform) |
[[0,1],[1,0]] |
internal node + four leaves: TL=0, TR=1, BL=1, BR=0 |
[[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]] |
internal node + four uniform-quadrant leaves: TL=1, TR=0, BL=0, BR=1 |
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson