246. Construct Quad Tree

A quadrant is either uniform — in which case one leaf describes it exactly — or it is mixed, in which case the only way to describe it is to split it into its four equal sub-quadrants and describe each recursively. That 'uniform → leaf, else split into four' rule is the entire construction, applied top-down.

The recursive rule

Define build(row, col, size) to construct the Quad-Tree for the size × size square whose top-left corner is (row, col).

1. Uniform check. Scan the square. If every cell equals the top-left cell, the whole region is one value — return a leaf whose val is that value (isLeaf = true).
2. Otherwise split. The region has mixed values, so it can't be a single leaf. Create an internal node and recurse into the four quadrants, each of side size / 2:
   • topLeft = build(row, col, half)
   • topRight = build(row, col + half, half)
   • bottomLeft = build(row + half, col, half)
   • bottomRight = build(row + half, col + half, half)

Because n is a power of two, half is always a whole number, and the recursion bottoms out at size == 1 (a single cell is always uniform, hence a leaf).

Why this is correct

Every region is handled by exactly one of the two cases. Uniform regions become leaves — the most compact possible description. Mixed regions must be subdivided, and subdividing into four equal quadrants is the Quad-Tree's defining operation. A single cell can never be mixed, so recursion always terminates.

Serialization

We return the tree in level order: enqueue the root, and repeatedly dequeue a node, emit [isLeaf, val] (as 1/0), and — if it's internal — enqueue its four children (topLeft, topRight, bottomLeft, bottomRight). A valid Quad-Tree has no null children, so the output is a clean list of pairs.

Worked example: grid = [[0,1],[1,0]]

The full 2×2 square is not uniform (it has both 0s and 1s), so the root is internal. half = 1, so each quadrant is a single cell — all leaves:

• topLeft = (0,0) = 0 → [1, 0]
• topRight = (0,1) = 1 → [1, 1]
• bottomLeft = (1,0) = 1 → [1, 1]
• bottomRight = (1,1) = 0 → [1, 0]

Level-order: root [0, 1], then its four children. Result: [[0,1],[1,0],[1,1],[1,1],[1,0]].

Complexity

• Time: each build scans its region for the uniform check. In the worst case (fully mixed) this gives the recurrence T(n²) = 4·T(n²/4) + O(n²), i.e. O(n² · log n).
• Space: O(log n) recursion depth plus the output tree.

import java.util.*;

class Solution {
    static class QuadNode {
        boolean val, isLeaf;
        QuadNode[] children = new QuadNode[4];
        QuadNode(boolean val, boolean isLeaf) { this.val = val; this.isLeaf = isLeaf; }
    }

    public int[][] construct(int[][] grid) {
        QuadNode root = build(grid, 0, 0, grid.length);
        List<int[]> result = new ArrayList<>();
        Deque<QuadNode> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()) {
            QuadNode node = q.poll();
            result.add(new int[]{node.isLeaf ? 1 : 0, node.val ? 1 : 0});
            if (!node.isLeaf) {
                for (QuadNode ch : node.children) q.add(ch);
            }
        }
        return result.toArray(new int[0][]);
    }

    private QuadNode build(int[][] grid, int r, int c, int size) {
        int first = grid[r][c];
        boolean uniform = true;
        outer:
        for (int i = r; i < r + size; i++) {
            for (int j = c; j < c + size; j++) {
                if (grid[i][j] != first) { uniform = false; break outer; }
            }
        }
        if (uniform) return new QuadNode(first == 1, true);
        int half = size / 2;
        QuadNode node = new QuadNode(true, false);
        node.children[0] = build(grid, r, c, half);
        node.children[1] = build(grid, r, c + half, half);
        node.children[2] = build(grid, r + half, c, half);
        node.children[3] = build(grid, r + half, c + half, half);
        return node;
    }
}