Construct Quad Tree — LC 427 Divide and Conquer Grid

Problem Statement#

LeetCode 427 — Construct Quad Tree | Difficulty: Medium

Given an n x n binary matrix grid where n is a power of 2, construct a Quad Tree from the grid. A QuadTree node has:

• isLeaf = true if this node represents a uniform region (all 0s or all 1s)
• val = the value of the region (1 or 0) for leaf nodes
• topLeft, topRight, bottomLeft, bottomRight = four child quadrants (null if leaf)

Constraints:

• n == grid.length == grid[i].length
• 1 <= n <= 64
• n is a power of 2
• grid[i][j] is either 0 or 1

Input:  grid = [[0,1],[1,0]]
Output: [[0,1],[1,0],[1,1],[1,1],[1,0]]

Input:  grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
Output: [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]

Why This Problem Matters#

Quad Trees are a fundamental data structure in computer graphics, geographic information systems (GIS), and image compression. Amazon and Google ask this problem because it tests divide-and-conquer reasoning on 2D grids — the same technique used in merge sort, binary search trees, and spatial data structures like k-d trees and R-trees.

The problem teaches the "check if uniform, then recurse" pattern that generalizes to many spatial partitioning problems. The naive O(n^4) approach (check uniformity for every possible region) is avoided by recursively subdividing only non-uniform regions.

The Core Insight#

For any rectangular region:

1. Check if the entire region is uniform (all same value)
2. If uniform: create a leaf node with that value — no children needed
3. If not uniform: create an internal node and recurse on the four equal quadrants (top-left, top-right, bottom-left, bottom-right)

The recursion terminates when either:

• The region is uniform (leaf node), or
• The region is 1x1 (single cell, always uniform by definition)

The uniformity check requires scanning all cells in the region, which makes the naive approach O(n^2) per check. With prefix sums, this can be reduced to O(1) per check, improving overall complexity.

Visual Dry Run#

Grid: [[0,1],[1,0]], size = 2

Root: internal node with four leaf children.

Solution (Optimal)#

class Solution:
    def construct(self, grid: list) -> 'Node':
        n = len(grid)
 
        def build(r, c, size):
            # Check if region is uniform
            val = grid[r][c]
            uniform = all(
                grid[r + i][c + j] == val
                for i in range(size)
                for j in range(size)
            )
 
            if uniform:
                # Leaf node: no children needed
                return Node(val == 1, True)
 
            # Not uniform: split into four equal quadrants
            half = size // 2
            node = Node(True, False)  # internal node
            node.topLeft     = build(r,          c,          half)
            node.topRight    = build(r,          c + half,   half)
            node.bottomLeft  = build(r + half,   c,          half)
            node.bottomRight = build(r + half,   c + half,   half)
            return node
 
        return build(0, 0, n)

var construct = function(grid) {
    const n = grid.length;
 
    function build(r, c, size) {
        const val = grid[r][c];
        let uniform = true;
 
        outer: for (let i = r; i < r + size; i++) {
            for (let j = c; j < c + size; j++) {
                if (grid[i][j] !== val) {
                    uniform = false;
                    break outer;
                }
            }
        }
 
        if (uniform) return new Node(val === 1, true);
 
        const half = size >> 1;  // size / 2
        const node = new Node(true, false);
        node.topLeft     = build(r,          c,          half);
        node.topRight    = build(r,          c + half,   half);
        node.bottomLeft  = build(r + half,   c,          half);
        node.bottomRight = build(r + half,   c + half,   half);
        return node;
    }
 
    return build(0, 0, n);
};

Time: O(n^2 log n) — O(log n) levels of recursion, each level processes O(n^2) cells total Space: O(log n) — recursion stack depth; the output tree has O(n^2) nodes in the worst case

Common Mistakes#

• Setting isLeaf = false for internal nodes but forgetting to assign children — always assign all four children for internal nodes
• Using size n//2 at each level but passing the wrong r and c offsets for the four quadrants
• Checking uniformity only at 1x1 cells — you must check at every level, not just at the leaf level
• Confusing val = 1 vs val == True — the Node val field stores a boolean, not the grid integer

Interview Tips#

• State the divide-and-conquer approach: check if uniform, if yes create a leaf, if no split into four
• Mention the O(1) uniformity check optimization using 2D prefix sums if asked about optimization
• Explain that n is always a power of 2, guaranteeing clean division at every level
• Real-world applications: image quadtrees for compression, GIS spatial indexing, collision detection

Follow-up Questions#

• How can you optimize the uniformity check to O(1)? Precompute a 2D prefix sum array; then sum of any rectangle can be computed in O(1). If sum equals 0 or (size * size), the region is uniform.
• What is the maximum number of nodes in a quad tree for an n x n grid? In the worst case (alternating 0s and 1s), O(n^2) leaf nodes and O(n^2) internal nodes.
• How would you reconstruct the grid from the quad tree? DFS on the tree — leaf nodes fill their entire region with val; internal nodes recurse on four quadrants.
• How does this differ from a k-d tree? k-d trees partition along alternating axes for point data; quad trees always partition into four equal quadrants for 2D grid data.

Key Takeaways#

• Quad Tree construction: if the region is uniform, create a leaf; otherwise recurse on four equal quadrants
• The base case is either a uniform region or a 1x1 cell — both become leaf nodes
• Four quadrants: top-left (r, c), top-right (r, c+half), bottom-left (r+half, c), bottom-right (r+half, c+half) with size half = size/2
• Time O(n^2 log n): O(log n) recursion depth, O(n^2) total work per level; Space O(log n) stack
• Optimization: 2D prefix sums reduce uniformity check from O(size^2) to O(1), improving total time to O(n^2)
• Real applications: image compression (run-length encoding on quadrants), GIS spatial indexing, game collision detection
• This divide-and-conquer on 2D grids pattern applies to many spatial problems beyond quad trees