Construct Quad Tree

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

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.

Approach 1 — Brute force: scan every square for uniformity

Follow 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


def construct(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 recursion levels rescans, in the worst case, all n^2 cells; O(log n) recursion depth. With n <= 64 (~4096 cells across 6 levels) this runs fast enough, but the rescanning is redundant work that the versions below eliminate.

Approach 2 — Bottom-up build with merge (canonical)

No uniformity scan is needed. 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 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


def construct(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):

1. build(0,0,4) splits into four build(.,.,2) calls.
2. build(0,0,2) (top-left quadrant, all 1s): its four 1x1 leaves are all val=1 leaves → merged into one leaf 1.
3. Similarly build(0,2,2) merges to leaf 0, build(2,0,2) to leaf 0, build(2,2,2) to leaf 1.
4. Back at the root: four leaves but values 1,0,0,1 differ → internal node with those four leaf children. Matches the expected output.

flowchart TD
    root["root: internal (isLeaf=False)"]
    tl["topLeft: leaf val=1"]
    tr["topRight: leaf val=0"]
    bl["bottomLeft: leaf val=0"]
    br["bottomRight: leaf val=1"]
    root --> tl
    root --> tr
    root --> bl
    root --> br

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

A square is uniform iff its sum is 0 (all zeros) or size*size (all ones). A 2-D prefix-sum array (P[i][j] = sum of the rectangle from the origin to (i-1, j-1), so any rectangle sum is O(1) by inclusion-exclusion) answers that check in constant time. This keeps the 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


def construct(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).