Construct Quad Tree

medium tree divide and conquer grid

Problem

Given a n * n matrix grid of 0's and 1's only. We want to represent the grid with a Quad-Tree. Return the root of the Quad-Tree representing the grid.

Recurse with a square region. If every cell in the region shares the same value, return a leaf. Otherwise split into four equal quadrants, recurse on each, and return an internal node.

Inputgrid = [[1,1,0,0],[1,1,0,0],[1,1,1,1],[1,1,1,1]]

Outputinternal{TL=leaf 1, TR=leaf 0, BL=leaf 1, BR=leaf 1}

The top-right 2×2 is uniformly 0 — collapses to a leaf. Other quadrants are uniform 1s.

grid (rows by ';', power-of-2 size)

def construct(grid):
    def build(r, c, n):
        v = grid[r][c]
        uniform = all(grid[r + i][c + j] == v for i in range(n) for j in range(n))
        if uniform:
            return Node(bool(v), True)
        h = n // 2
        return Node(False, False,
            build(r, c, h), build(r, c + h, h),
            build(r + h, c, h), build(r + h, c + h, h))
    return build(0, 0, len(grid))

function construct(grid) {
  function build(r, c, n) {
    const v = grid[r][c];
    let uniform = true;
    outer: for (let i = 0; i < n; i++)
      for (let j = 0; j < n; j++)
        if (grid[r + i][c + j] !== v) { uniform = false; break outer; }
    if (uniform) return { val: !!v, isLeaf: true };
    const h = n >> 1;
    return { val: false, isLeaf: false,
      tl: build(r, c, h), tr: build(r, c + h, h),
      bl: build(r + h, c, h), br: build(r + h, c + h, h) };
  }
  return build(0, 0, grid.length);
}

public Node construct(int[][] grid) {
    return build(grid, 0, 0, grid.length);
}
Node build(int[][] g, int r, int c, int n) {
    int v = g[r][c]; boolean uniform = true;
    for (int i = 0; i < n && uniform; i++)
        for (int j = 0; j < n; j++)
            if (g[r + i][c + j] != v) { uniform = false; break; }
    if (uniform) return new Node(v == 1, true);
    int h = n / 2;
    return new Node(false, 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));
}

Node* build(vector<vector<int>>& g, int r, int c, int n) {
    int v = g[r][c]; bool uniform = true;
    for (int i = 0; i < n && uniform; i++)
        for (int j = 0; j < n; j++)
            if (g[r + i][c + j] != v) { uniform = false; break; }
    if (uniform) return new Node(v == 1, true);
    int h = n / 2;
    return new Node(false, 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));
}
Node* construct(vector<vector<int>>& grid) {
    return build(grid, 0, 0, (int)grid.size());
}

Explanation

A quadtree compresses an n×n grid of 0s and 1s by collapsing any square that is all the same value into a single leaf. We build it with divide and conquer: look at a square region and either make it a leaf or split it into four smaller squares.

The helper build(r, c, n) handles the square whose top-left corner is (r, c) with side length n. It checks whether every cell equals the first cell's value v. If the region is uniform, we return a leaf carrying that value.

If the region is mixed, we halve the side (h = n / 2) and recurse on the four quadrants — top-left, top-right, bottom-left, bottom-right — then return an internal node holding those four children.

Example: grid [[1,1,0,0],[1,1,0,0],[1,1,1,1],[1,1,1,1]]. The whole 4×4 is mixed, so it splits. The top-left 2×2 is all 1s (leaf 1), the top-right 2×2 is all 0s (leaf 0), and the bottom two 2×2 blocks are all 1s (leaf 1 each).

This works because a uniform block needs no detail, so recursion stops early and large flat areas turn into a single node instead of many cells.

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