Construct Quad Tree

Medium#427four quarters

You get an n×n grid of 0s and 1s, n a power of two. Build its quad tree: a square of one value is a leaf with that value; any other square is a node whose four children are its top-left, top-right, bottom-left and bottom-right quarters. Our grid, row by row: 1101, 1111, 0000, 0000 — the root is a node; its top-left quarter is a leaf 1, the bottom ones are leaves 0, and the top-right one is a node with leaves 0, 1, 1, 1.

427 Construct Quad TreeWalkthrough · 1×

Example: build the quad tree of a 4×4 grid: split down to single cells, then join four equal leaves into one on the way back.

1101111100000000
cell not reached yetsquare of the current callcurrent callwaiting for its quartersbuilt: a leaf covers its whole squarefour equal leaves joining into one

Build the tree for the whole 4×4 grid: build(0, 0, 4)

01/53
restart · back · play · step
Speed
1function construct(grid):
2 return build(0, 0, len(grid))
3
4function build(r, c, size):
5 if size == 1:
6 return leaf(grid[r][c])
7 half = size / 2
8 tl = build(r, c, half)
9 tr = build(r, c + half, half)
10 bl = build(r + half, c, half)
11 br = build(r + half, c + half, half)
12 if tl, tr, bl and br are leaves with one value:
13 return leaf(tl.val)
14 return node(tl, tr, bl, br)
state
r
–
c
–
size
–
half
–
click a step to go back

← → step · space play/pause

Why it works

  1. Every quarter is the same problem on a square half as wide, and a single cell is always a leaf: the recursion always reaches an answer.
  2. A square is all one value exactly when its four quarters are all leaves with that value, so checking the four children is enough: no cell is looked at twice.
  3. A quarter that holds both values comes back as a node, and then its parent has to stay a node too.

Complexity

Time O(n²): each cell becomes a leaf once, and each larger square only compares its four children. Memory O(log n) besides the tree: the call stack is as deep as the number of halvings.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.