Solving tips
- Let the recursion parameters describe a square by its top-left corner (r,c) and side length, mirroring the recursive shape of the output node itself.
- Cleanest approach: recurse straight down to 1x1 leaves and merge on the way up — if all four children are leaves with equal values, collapse them into one leaf; this touches each cell once for O(n^2).
- Alternatively use a 2-D prefix sum so a square is a leaf iff its sum is 0 or size*size, giving an O(1) uniformity test in a top-down build.
- Pitfall: keep quadrant order straight — (r, c+half) is topRight and (r+half, c) is bottomLeft — and require BOTH all-leaves AND equal-values before merging.
Problem
You are given an n x n binary grid (every cell is 0 or 1, and n is a power of two). Represent it as a quad tree:
- Each node has a boolean
val and a boolean isLeaf, plus four children: topLeft, topRight, bottomLeft, bottomRight.
- If a grid region is uniform (all 0s or all 1s), it becomes a leaf node with
isLeaf = True and val set to that value, and no children.
- Otherwise the node has
isLeaf = False (its val may be either — graders accept both), and the region is split into four equal quadrants, each represented recursively by the corresponding child.
Return the root of the quad tree for the whole grid.
Examples
Example 1
Input: grid = [[0, 1],
[1, 0]]
Output: root(isLeaf=False) with four leaf children:
topLeft=0, topRight=1, bottomLeft=1, bottomRight=0
The 2x2 grid is mixed, so it splits once into four single-cell leaves.
Example 2
Input: grid = [[1, 1],
[1, 1]]
Output: a single leaf node with val = 1
The whole grid is uniform — no split needed.
Example 3
Input: grid = [[1, 1, 0, 0],
[1, 1, 0, 0],
[0, 0, 1, 1],
[0, 0, 1, 1]]
Output: root(isLeaf=False) with four LEAF children:
topLeft=1, topRight=0, bottomLeft=0, bottomRight=1
Each 2x2 quadrant is uniform, so the tree stops after one split.
Constraints
n == grid.length == grid[i].length, 1 <= n <= 64, and n is a power of 2.grid[i][j] is 0 or 1.- Expected complexity:
O(n^2) cells exist, so O(n^2)–O(n^2 log n) time is fine at this size.
Think about it first
Hint 1
The structure of the output (a node whose four children describe four sub-squares) mirrors a recursion shape exactly. What are the recursion's parameters?
Hint 2
Describe any sub-square by its top-left corner `(row, col)` and side length. Base decision: is this square uniform? If yes, leaf; if no, recurse on the four half-size quadrants.
Hint 3
You can skip the explicit "is it uniform?" scan: recurse all the way down to 1x1 leaves, and on the way back up, if all four children are leaves with the same value, merge them into one leaf. (A prefix-sum over the grid is the other way to test uniformity in O(1).)
TL;DR
Top-down recursion over quadrants with a uniformity check — O(n^2 log n) naive, O(n^2) with bottom-up merging or prefix sums; O(log n) recursion depth.
The naive intuition follows the definition literally: for the current square, scan all its cells. If they match, emit a leaf; otherwise split into four quadrants and recurse.
# Definition for a QuadTree node.
# class Node:
# def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
# self.val = val
# self.isLeaf = isLeaf
# self.topLeft = topLeft
# self.topRight = topRight
# self.bottomLeft = bottomLeft
# self.bottomRight = bottomRight
from typing import List
class Solution:
def construct(self, grid: List[List[int]]) -> 'Node':
def uniform(r: int, c: int, size: int) -> bool:
first = grid[r][c]
for i in range(r, r + size):
for j in range(c, c + size):
if grid[i][j] != first:
return False
return True
def build(r: int, c: int, size: int) -> 'Node':
if uniform(r, c, size):
return Node(grid[r][c] == 1, True, None, None, None, None)
half = size // 2
return Node(
True, False,
build(r, c, half),
build(r, c + half, half),
build(r + half, c, half),
build(r + half, c + half, half),
)
return build(0, 0, len(grid))
Complexity: O(n^2 log n) time — each of the log n levels of the recursion rescans (in the worst case) all n^2 cells; O(log n) recursion depth. With n <= 64 (~4096 cells x 6 levels) this is trivially fast — the constraint doesn’t kill it, but the rescanning is pure waste and the cleaner versions below remove it.
Approach 2 — Bottom-up build with merge (canonical)
The insight: you don’t need any uniformity scan. Recurse straight down to 1x1 squares (always leaves), and while returning, check whether the four children are all leaves sharing one value — if so, collapse them into a single leaf. Every cell is then touched exactly once.
# Definition for a QuadTree node.
# class Node:
# def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
# self.val = val
# self.isLeaf = isLeaf
# self.topLeft = topLeft
# self.topRight = topRight
# self.bottomLeft = bottomLeft
# self.bottomRight = bottomRight
from typing import List
class Solution:
def construct(self, grid: List[List[int]]) -> 'Node':
def build(r: int, c: int, size: int) -> 'Node':
if size == 1:
return Node(grid[r][c] == 1, True, None, None, None, None)
half = size // 2
tl = build(r, c, half)
tr = build(r, c + half, half)
bl = build(r + half, c, half)
br = build(r + half, c + half, half)
if (tl.isLeaf and tr.isLeaf and bl.isLeaf and br.isLeaf
and tl.val == tr.val == bl.val == br.val):
return Node(tl.val, True, None, None, None, None)
return Node(True, False, tl, tr, bl, br)
return build(0, 0, len(grid))
Walkthrough on Example 3 (the 4x4 block-diagonal grid):
build(0,0,4) splits into four build(.,.,2) calls.build(0,0,2) (top-left quadrant, all 1s): its four 1x1 leaves are all val=1 leaves → merged into one leaf 1.- Similarly
build(0,2,2) merges to leaf 0, build(2,0,2) to leaf 0, build(2,2,2) to leaf 1.
- Back at the root: four leaves but values
1,0,0,1 differ → internal node with those four leaf children. Matches the expected output.
Complexity: O(n^2) time — the recursion visits each cell once at the bottom and does O(1) merge work at each of the O(n^2 / 3) internal candidates; O(log n) auxiliary space for the recursion stack (output tree not counted).
Approach 3 — Top-down with a 2-D prefix sum
The insight: a square is uniform iff its sum is 0 (all zeros) or size*size (all ones). A 2-D prefix-sum array (a classical technique: P[i][j] = sum of the rectangle from the origin to (i-1, j-1), letting any rectangle sum be computed in O(1) by inclusion-exclusion) answers that check in constant time, keeping the intuitive top-down shape of Approach 1 without its rescans.
# Definition for a QuadTree node.
# class Node:
# def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
# self.val = val
# self.isLeaf = isLeaf
# self.topLeft = topLeft
# self.topRight = topRight
# self.bottomLeft = bottomLeft
# self.bottomRight = bottomRight
from typing import List
class Solution:
def construct(self, grid: List[List[int]]) -> 'Node':
n = len(grid)
pre = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n):
for j in range(n):
pre[i + 1][j + 1] = (pre[i][j + 1] + pre[i + 1][j]
- pre[i][j] + grid[i][j])
def square_sum(r: int, c: int, size: int) -> int:
return (pre[r + size][c + size] - pre[r][c + size]
- pre[r + size][c] + pre[r][c])
def build(r: int, c: int, size: int) -> 'Node':
total = square_sum(r, c, size)
if total == 0:
return Node(False, True, None, None, None, None)
if total == size * size:
return Node(True, True, None, None, None, None)
half = size // 2
return Node(
True, False,
build(r, c, half),
build(r, c + half, half),
build(r + half, c, half),
build(r + half, c + half, half),
)
return build(0, 0, n)
Walkthrough on Example 1 ([[0,1],[1,0]]): prefix sums give square_sum(0,0,2) = 2, which is neither 0 nor 4 → split. The four 1x1 sums are 0, 1, 1, 0 → leaves 0, 1, 1, 0. Same output as expected.
Complexity: O(n^2) time (O(n^2) to build the prefix table, O(1) per recursion node, and the recursion has O(n^2) nodes in the worst checkerboard case); O(n^2) space for the prefix table.
Common pitfalls
- Swapping
bottomLeft and topRight when recursing — the quadrant at (r, c + half) is topRight, and (r + half, c) is bottomLeft.
- Forgetting the merge condition needs both checks: all four children are leaves and all four values are equal (four leaves with mixed values must stay split).
- Treating
val on internal nodes as meaningful — the problem accepts either value for non-leaves, so don’t contort logic to compute one.
- Recursing with the wrong size (
size // 2 applied inconsistently) so quadrants overlap or miss cells — off-by-ones here silently produce a wrong tree, not a crash.
Pattern takeaway
When the output data structure is itself recursive over a spatial split (quad trees, segment trees, k-d trees), let the recursion parameters describe the region — corner plus size — and make the structural decision at each level. The efficiency lever is always the same: replace the per-level “inspect the whole region” test with either information returned from children (bottom-up merge) or a precomputed O(1) region query (prefix sums).