Build a Quadtree From a Grid

medium tree divide and conquer grid

Problem

Given an n × n grid where n is a power of two and each cell is 0 or 1, build a quadtree. Each node is either a leaf carrying a value, or an internal node with four children for the top-left, top-right, bottom-left, and bottom-right quadrants.

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());
}

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