Construct Quad Tree

Given an n x n binary grid where n is a power of two, construct a quad tree representing the grid. A region becomes a leaf if all its values are the same; otherwise it splits into four equal quadrants.

Why this is worth learning

A recursive call owns one square region. It may compress that region into one leaf only after proving all its cells equal; otherwise the four child regions partition it exactly.

Before coding: one-minute experiment

For grid [[1,1],[1,0]], why must the root be internal, and what are its four leaf values in quadrant order?

Function signature

type Node struct { ... }
func Construct(grid [][]int) *Node

Inputs / outputs

• grid: square binary matrix with size power of two.
• Return: root of the quad tree.

Example

grid = [[0,1],[1,0]]
Not uniform, so root is not leaf and has four leaf children.

Constraints

• n == len(grid) == len(grid[i])
• n is a power of two.
• Values are 0 or 1.

Core idea (near-solution)

Recursively process a square region. If every cell has the same value, return a leaf node. Otherwise split into top-left, top-right, bottom-left, and bottom-right quadrants.

Invariant: build(r, c, size) returns a quad tree representing exactly that square region.

Algorithm (step-by-step)

1. Check whether all cells in the current region equal grid[r][c].
2. If uniform, return a leaf node with that value.
3. Otherwise, split size in half.
4. Recursively build four quadrants.
5. Return an internal node with the four child pointers.

Correctness sketch

A size-one binary square is necessarily uniform and becomes a leaf with its cell value. For a larger region, the uniformity scan is exact: a leaf is emitted only when no different cell exists. If a difference is found, four half-size quadrants are disjoint and cover the region. By induction each child exactly represents its quadrant, so their ordered combination represents the whole square. Recursion terminates because a positive power-of-two size halves until one. Leaf children are nil, and nonleaf quadrant positions are semantically distinct; swapping them changes the represented image.

Trace (hand walkthrough)

2x2 mixed grid:
[0,1]
[1,0]
whole region mixed -> split into four 1x1 regions
each 1x1 region is uniform -> four leaves

Pitfalls to avoid

• Mixing up quadrant coordinates.
• Returning a leaf for the first cell without checking the full region.
• Forgetting that internal node Val is arbitrary in the usual problem contract.

Debugging lens

Check reconstruction of every original cell and whether each uniform region is compressed. The nonleaf Val field is not the region’s majority; the reference keeps it true as an existing representation convention.

Complexity

• Time: O(n^2 log n) with direct uniform scans at each level in the worst case; can be improved with prefix sums.
• Extra space: O(log n) recursion depth plus output nodes.

Implementation notes (Go)

• Use bool for Val: grid[r][c] == 1.
• Be explicit about quadrant offsets: (r,c), (r,c+half), (r+half,c), (r+half,c+half).

Contract precision

The input has positive power-of-two side length and rectangular binary rows. The reference does not mutate the grid. For internal nodes, Val is retained as true; meaningful cell values come from leaves.

Reconstruction checkpoint

For grid [[1,1],[1,0]], why must the root be internal, and what are its four leaf values in quadrant order?

Return to Divide & Conquer · Module quiz