AlgoMaster Logo

Construct Quad Tree

mediumFrequency8 min readUpdated June 23, 2026

Understanding the Problem

We are given a square grid of 0s and 1s, and we need to build a Quad-Tree that represents this grid. A Quad-Tree stores the grid region by region: if a region is uniform (all the same value), it becomes a single leaf node. If a region has mixed values, it splits into four equal quadrants, one child per quadrant, and the same rule applies to each.

The same structure appears in image compression. A block of pixels that is all one color is stored as a single entry, "this entire block is color X", and only mixed blocks get subdivided further.

The problem comes with guarantees that simplify the recursion:

  • The grid size is always a power of 2, which guarantees we can always split evenly into four quadrants.
  • The recursion bottoms out when either the region is uniform or we reach a single cell (which is trivially uniform).
  • The four children are always in the order: top-left, top-right, bottom-left, bottom-right.

Key Constraints:

  • 1 <= n <= 64 and n is a power of 2 → The grid is tiny. Even an O(n^2 log n) brute force is at most ~24,576 operations. Performance is not a concern here, so the focus is on correctness and clean recursion.
  • grid[i][j] is either 0 or 1 → With only two possible values, a region is uniform when every cell matches the first cell, and the sum of a region determines uniformity (this matters for Approach 2).

Approach 1: Recursive Brute Force

Intuition

The problem description already states the algorithm: check if the region is uniform, and if not, split into four quadrants and recurse. The brute force is a direct translation of that definition.

For any given sub-grid, we scan every cell to see if they are all the same value. If yes, we create a leaf node. If not, we divide the grid into four equal parts and recursively build a Quad-Tree node for each part. The current node becomes an internal node (isLeaf = false) with those four children.

The only bookkeeping is the coordinates. We identify each sub-grid by its top-left corner (row, col) and its side length. When we subdivide, each child covers half the side length, and the four corners are (row, col), (row, col + half), (row + half, col), and (row + half, col + half).

Algorithm

  1. Define a helper function build(row, col, size) that constructs the Quad-Tree for the sub-grid starting at (row, col) with the given side length.
  2. Scan all cells in the sub-grid to check if every value is the same.
  3. If the sub-grid is uniform, return a leaf node with that value.
  4. Otherwise, compute half = size / 2 and recursively build four children:
    • Top-left: build(row, col, half)
    • Top-right: build(row, col + half, half)
    • Bottom-left: build(row + half, col, half)
    • Bottom-right: build(row + half, col + half, half)
  5. Return an internal node with isLeaf = false and these four children.

Example Walkthrough

1build(row=0, col=0, size=2): scan entire 2x2 grid for uniformity
0
1
0
scan
0
1
1
1
0
1/7

Code

The bottleneck is the uniformity scan: the same cells get re-read at every recursion level. The next approach replaces that scan with an O(1) lookup.

Approach 2: Optimized with Prefix Sum

Intuition

In a binary grid, uniformity is a question about the sum: a sub-grid of side size is all zeros when its sum is 0, and all ones when its sum is size * size. Anything in between means the region is mixed. Computing that sum in O(1) removes the scan entirely.

A 2D prefix sum provides the O(1) sum. We precompute a matrix where prefix[i][j] holds the sum of all cells in the rectangle from (0,0) to (i-1, j-1). Then, the sum of any sub-rectangle follows from inclusion-exclusion:

sum(row, col, size) = prefix[row+size][col+size] - prefix[row][col+size] - prefix[row+size][col] + prefix[row][col]

The recursion itself stays identical to the brute force. Only the uniformity check changes, from an O(size^2) scan to one subtraction-based lookup.

Algorithm

  1. Build a 2D prefix sum array from the grid.
  2. Define a helper function build(row, col, size) that constructs the Quad-Tree for the sub-grid starting at (row, col) with the given side length.
  3. Compute the sum of the sub-grid using the prefix sum in O(1).
  4. If the sum is 0, return a leaf node with val = false.
  5. If the sum equals size * size, return a leaf node with val = true.
  6. Otherwise, compute half = size / 2 and recursively build four children.
  7. Return an internal node with these four children.

Example Walkthrough

1build(0,0,4): regionSum=8, total=16 → 8!=0 and 8!=16, mixed → subdivide
0
1
2
3
0
1
1
0
0
1
1
1
0
0
2
0
0
1
1
3
0
0
1
1
1/6

Code

The prefix sum spends O(n^2) extra memory to answer one question: is this region uniform? Building the tree bottom-up answers the same question with no auxiliary structure.

Approach 3: Bottom-Up Merge

Intuition

Both previous approaches decide whether a region is uniform before recursing into it. The decision can also be postponed: recurse all the way down to single cells, then merge on the way back up. Build the four children first. If all four come back as leaves carrying the same value, the region they cover is uniform, so discard them and return a single leaf in their place. Otherwise, keep them under an internal node.

Merging only leaf children is sufficient because uniformity propagates upward. If a region is uniform, each of its four quadrants is uniform, so by induction each child returns as a leaf with the same value and the merge fires. The merged leaf is then itself a candidate for merging one level higher. The resulting tree is identical to the one the top-down approaches build.

This removes both the repeated scans of Approach 1 and the prefix array of Approach 2. The only extra memory is the recursion stack.

Algorithm

  1. Define a helper function build(row, col, size).
  2. If size is 1, return a leaf node with the value of the single cell grid[row][col].
  3. Otherwise, compute half = size / 2 and recursively build the four children:
    • Top-left: build(row, col, half)
    • Top-right: build(row, col + half, half)
    • Bottom-left: build(row + half, col, half)
    • Bottom-right: build(row + half, col + half, half)
  4. If all four children are leaves with the same val, return a single leaf node with that value.
  5. Otherwise, return an internal node with isLeaf = false and these four children.

Example Walkthrough

1build(0,0,4): size > 1, no uniformity check, recurse straight into four 2x2 quadrants
0
1
2
3
0
1
1
0
0
1
1
1
0
0
2
0
0
1
1
3
0
0
1
1
1/7

Code

Approach 2 stops recursing as soon as a region is uniform, while this approach descends to single cells even inside uniform blocks, creating nodes it then discards. Both run in O(n^2) time. The difference is memory: the prefix sum costs O(n^2) extra space, while the merge needs only the recursion stack.