Construct Quad Tree

MediumDivide & Conquer · Recursion on Quadrants🧩 Recursion & Divide and Conquer LeetCode #427 ↗Updated Oct 30, 2026

Problem

You are given an n × n grid of 0s and 1s, where n is a power of two. Encode it as a quad tree: if a square region holds a single value it becomes a leaf (isLeaf = true, val = that value); otherwise it is an internal node whose four children encode its top-left, top-right, bottom-left and bottom-right quarters. Return the root (an internal node's val may be anything).

Input[[0,1],[1,0]]Outputinternal root; leaves TL=0, TR=1, BL=1, BR=0

Input[[1,1],[1,1]]Outputone leaf, val = 1

Input[[1,1,0,0],[1,1,0,0],[0,0,0,1],[0,0,1,1]]Outputroot: TL=leaf 1, TR=leaf 0, BL=leaf 0, BR=internal(0,1,1,1)

n = 2^x, 0 ≤ x ≤ 6 · grid[i][j] ∈ {0, 1}

Try it yourself

Java

class Solution {
    public Node construct(int[][] grid) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A region is a leaf exactly when its four quarters are leaves with the same value. Building bottom-up lets each parent decide in O(1) from its children, so no cell is ever re-scanned.

PatternRecursion & Divide and Conquer

Instinct If the answer for n items can be built from the same problem on halves (or smaller pieces) plus a cheap combine step - split, recurse, merge.

Memory hack Split it, trust it, stitch it - nail the base case, take the leap of faith on smaller calls, then glue their answers together.

Open the Recursion & Divide and Conquer guide →

Approaches

Brute ForceTop-Down, Scan Each Region

Time O(n² log n)Space O(log n)

For a square, scan all its cells. If they match, return a leaf; otherwise split into four quarters and recurse. Each of the log n levels can scan up to all n² cells again.

Java

public Node construct(int[][] grid) {
    return build(grid, 0, 0, grid.length);
}
private Node build(int[][] g, int r, int c, int size) {
    if (isUniform(g, r, c, size)) return new Node(g[r][c] == 1, true);
    int h = size / 2;
    return new Node(true, false,
            build(g, r, c, h), build(g, r, c + h, h),
            build(g, r + h, c, h), build(g, r + h, c + h, h));
}
private boolean isUniform(int[][] g, int r, int c, int size) {
    for (int i = r; i < r + size; i++) {
        for (int j = c; j < c + size; j++) {
            if (g[i][j] != g[r][c]) return false;
        }
    }
    return true;
}

Direct translation of the definition; repeated scans add a log factor.

BetterTop-Down with 2D Prefix Sums

Time O(n²)Space O(n²)

Precompute a 2D prefix-sum table so the number of 1s in any square comes out in O(1). A square is uniform when that count is 0 or size². The recursion visits O(n²) regions in total and each check is constant time.

Java

private int[][] pre;
public Node construct(int[][] grid) {
    int n = grid.length;
    pre = new int[n + 1][n + 1];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            pre[i + 1][j + 1] = grid[i][j] + pre[i][j + 1] + pre[i + 1][j] - pre[i][j];
        }
    }
    return build(0, 0, n);
}
private Node build(int r, int c, int size) {
    int ones = pre[r + size][c + size] - pre[r][c + size] - pre[r + size][c] + pre[r][c];
    if (ones == 0) return new Node(false, true);
    if (ones == size * size) return new Node(true, true);
    int h = size / 2;
    return new Node(true, false,
            build(r, c, h), build(r, c + h, h),
            build(r + h, c, h), build(r + h, c + h, h));
}

Removes the log factor, but spends an extra (n+1)² table.

OptimalBottom-Up Merge of Quadrants

Time O(n²)Space O(log n)

Recurse all the way to single cells (always leaves), then on the way back up merge: if the four children are leaves with equal val, replace them by one leaf, otherwise keep an internal node. Every cell is read exactly once and each merge is O(1); the only extra memory is the recursion stack.

Java

public Node construct(int[][] grid) {
    return build(grid, 0, 0, grid.length);
}
private Node build(int[][] g, int r, int c, int size) {
    if (size == 1) return new Node(g[r][c] == 1, true);
    int h = size / 2;
    Node tl = build(g, r, c, h), tr = build(g, r, c + h, h);
    Node bl = build(g, r + h, c, h), br = build(g, r + h, c + h, h);
    boolean allLeaves = tl.isLeaf && tr.isLeaf && bl.isLeaf && br.isLeaf;
    if (allLeaves && tl.val == tr.val && tr.val == bl.val && bl.val == br.val) {
        return new Node(tl.val, true); // four equal leaves collapse into one
    }
    return new Node(false, false, tl, tr, bl, br);
}

Linear in the grid size with no auxiliary table — best on both axes.

Pro tip

Keep child order fixed as TL, TR, BL, BR — mixing up the row/column offsets is the most common bug.

At a glance

Level	Approach	Time	Space
Brute Force	Top-Down, Scan Each Region	`O(n² log n)`	`O(log n)`
Better	Top-Down with 2D Prefix Sums	`O(n²)`	`O(n²)`
Optimal	Bottom-Up Merge of Quadrants	`O(n²)`	`O(log n)`

Common pitfalls

Swapping row and column offsets — top-right is (r, c + h), not (r + h, c).
Merging four leaves without checking they're all leaves — an internal child can carry any val.
Leaving children non-null on leaf nodes — leaves must have all four children null.

Interview tips

Clarify the Node fields and child order (TL, TR, BL, BR) before coding.
Start top-down with a scan, then mention prefix sums or the bottom-up merge.
State the recurrence T(n²) = 4T(n²/4) + O(1) for the bottom-up version.

Pattern

Divide & conquer on quadrants → 2D grids of size 2^k that are summarised region by region.

My notes saved in this browser