LeetCode 427 - Construct Quad Tree

LeetCode Problem 427

Difficulty: 🟡 Medium
Topics: Array, Divide and Conquer, Tree, Matrix

Solution

Problem Understanding

The problem asks us to convert a binary matrix into a Quad-Tree representation. A Quad-Tree is a recursive tree structure where every internal node has exactly four children, each representing one quadrant of the current square region.

The input is an n x n matrix called grid, where every value is either 0 or 1. The size n is guaranteed to be a power of two, which is important because it ensures the matrix can always be evenly divided into four equal sub-squares at every recursive step.

The output should be the root node of the constructed Quad-Tree. Each node contains:

• val, which represents the value of the region
• isLeaf, which tells whether the region is uniform
• four child pointers for the four quadrants

A node becomes a leaf node if the entire region it represents contains only identical values. For example, if a region consists entirely of 1s, then it can be compressed into a single leaf node with:

val = True
isLeaf = True

If the region contains both 0s and 1s, then it cannot be compressed. In that case, we create an internal node and recursively divide the region into:

• top-left
• top-right
• bottom-left
• bottom-right

The important observation is that the Quad-Tree is fundamentally a divide-and-conquer structure. Each recursive call handles one square portion of the matrix.

The constraints are relatively small:

• n <= 64
• n is always a power of two

Even though the matrix is small, inefficient repeated scanning can still create unnecessary overhead. The problem is mainly about implementing recursive subdivision correctly.

Several edge cases are important:

• A grid where every value is identical should produce exactly one leaf node.
• A checkerboard-style grid alternates values and forces subdivision all the way down to single cells.
• A 1 x 1 grid is already a leaf node and represents the smallest possible input.
• Internal nodes may use either True or False for val, because the problem explicitly states that val is ignored when isLeaf == False.

Approaches

Brute Force Approach

The brute-force approach recursively checks whether every sub-grid is uniform by scanning all cells inside the region.

For a given square region:

1. Iterate through every cell.
2. Compare all values against the first cell.
3. If every value matches, create a leaf node.
4. Otherwise, divide the region into four equal quadrants and recurse.

This works because every recursive call correctly determines whether a region can be compressed into a leaf or must be subdivided further.

However, the downside is repeated scanning. Large portions of the matrix may be revisited many times across recursive calls. In the worst case, such as a checkerboard pattern, every level performs repeated full scans.

Optimal Approach

The optimal recursive divide-and-conquer solution follows the same recursive structure but is carefully organized to avoid unnecessary overhead and keep the implementation clean.

The key insight is that Quad-Trees naturally correspond to recursive subdivision of square regions. Every recursive call only needs three pieces of information:

• starting row
• starting column
• current square size

The recursion mirrors the exact tree structure we are building. If a region is uniform, recursion stops immediately. Otherwise, the region is split into four smaller squares.

Because the maximum size is only 64 x 64, this recursive approach is efficient enough without requiring advanced optimizations such as prefix sums.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n² log n)	O(log n)	Repeatedly scans regions to check uniformity
Optimal	O(n² log n)	O(log n)	Recursive divide-and-conquer construction

Algorithm Walkthrough

1. Start with the entire grid.

The root node represents the full matrix, so the first recursive call covers the region starting at (0, 0) with size n. 2. Check whether the current region is uniform.

Scan every cell inside the current square region and compare each value against the first cell. If all values match, then the region can be compressed into a single leaf node. 3. Create a leaf node if the region is uniform.

If every value is identical:

• set isLeaf = True
• set val to the region value
• set all children to None

This becomes a terminal recursive case. 4. Divide non-uniform regions into four quadrants.

If the region contains mixed values, then we must subdivide it. Compute:

half = size // 2

Then recursively construct:

• top-left: (row, col)
• top-right: (row, col + half)
• bottom-left: (row + half, col)
• bottom-right: (row + half, col + half)

5. Create an internal node.

Internal nodes have:

• isLeaf = False
• any value for val
• four child pointers assigned from recursion

6. Return the constructed node.

Each recursive call returns the root node for its region, allowing the full Quad-Tree to assemble naturally from the bottom upward.

Why it works

The algorithm works because every recursive call correctly represents one square region of the matrix.

If a region is uniform, the Quad-Tree definition requires it to become a leaf node. If it is not uniform, the definition requires subdivision into exactly four equal quadrants. Since recursion applies the same logic to every sub-region, the resulting tree exactly matches the required Quad-Tree representation.

Python Solution

from typing import List

# Definition for a QuadTree node.
class Node:
    def __init__(
        self,
        val,
        isLeaf,
        topLeft,
        topRight,
        bottomLeft,
        bottomRight,
    ):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight

class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':
        n = len(grid)

        def build(row: int, col: int, size: int) -> Node:
            first_value = grid[row][col]
            is_uniform = True

            for r in range(row, row + size):
                for c in range(col, col + size):
                    if grid[r][c] != first_value:
                        is_uniform = False
                        break
                if not is_uniform:
                    break

            if is_uniform:
                return Node(
                    val=bool(first_value),
                    isLeaf=True,
                    topLeft=None,
                    topRight=None,
                    bottomLeft=None,
                    bottomRight=None,
                )

            half = size // 2

            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)

            return Node(
                val=True,
                isLeaf=False,
                topLeft=top_left,
                topRight=top_right,
                bottomLeft=bottom_left,
                bottomRight=bottom_right,
            )

        return build(0, 0, n)

The implementation follows the recursive divide-and-conquer structure directly.

The nested build() function constructs the Quad-Tree for one square region. Its parameters identify:

• the starting row
• the starting column
• the side length of the square

The first section checks whether the region is uniform. It scans every cell and compares against the first value in the region. If any mismatch is found, the region is not uniform.

If the region is uniform, the function immediately returns a leaf node.

Otherwise, the region is divided into four equal quadrants. Recursive calls build the child nodes for each quadrant. Finally, the current node becomes an internal node containing those four children.

The recursion naturally terminates because every subdivision reduces the region size by half, eventually reaching single-cell regions.

Go Solution

/**
 * Definition for a QuadTree node.
 * type Node struct {
 *     Val bool
 *     IsLeaf bool
 *     TopLeft *Node
 *     TopRight *Node
 *     BottomLeft *Node
 *     BottomRight *Node
 * }
 */

func construct(grid [][]int) *Node {
    n := len(grid)

    var build func(row, col, size int) *Node

    build = func(row, col, size int) *Node {
        firstValue := grid[row][col]
        isUniform := true

        for r := row; r < row+size; r++ {
            for c := col; c < col+size; c++ {
                if grid[r][c] != firstValue {
                    isUniform = false
                    break
                }
            }

            if !isUniform {
                break
            }
        }

        if isUniform {
            return &Node{
                Val:         firstValue == 1,
                IsLeaf:      true,
                TopLeft:     nil,
                TopRight:    nil,
                BottomLeft:  nil,
                BottomRight: nil,
            }
        }

        half := size / 2

        topLeft := build(row, col, half)
        topRight := build(row, col+half, half)
        bottomLeft := build(row+half, col, half)
        bottomRight := build(row+half, col+half, half)

        return &Node{
            Val:         true,
            IsLeaf:      false,
            TopLeft:     topLeft,
            TopRight:    topRight,
            BottomLeft:  bottomLeft,
            BottomRight: bottomRight,
        }
    }

    return build(0, 0, n)
}

The Go implementation mirrors the Python logic closely.

The main difference is memory handling. In Go, nodes are allocated using pointers with &Node{}. Child references use nil instead of None.

Boolean conversion also differs slightly. Since the grid contains integers, the expression:

firstValue == 1

converts the integer into a boolean.

Go recursion works naturally here because the recursion depth is small, at most log₂(64) = 6.

Worked Examples

Example 1

Input:

grid = [
  [0,1],
  [1,0]
]

Initial call:

build(0, 0, 2)

The region contains both 0 and 1, so it is not uniform.

The grid is divided into four 1 x 1 quadrants.

Quadrant	Coordinates	Value
Top Left	(0,0)	0
Top Right	(0,1)	1
Bottom Left	(1,0)	1
Bottom Right	(1,1)	0

Each quadrant becomes a leaf node because single cells are always uniform.

Resulting structure:

Root (internal)
├── TopLeft     -> leaf(0)
├── TopRight    -> leaf(1)
├── BottomLeft  -> leaf(1)
└── BottomRight -> leaf(0)

Example 2

Input:

[
 [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]
]

The full grid is not uniform.

Split into four 4 x 4 regions.

Region	Uniform?	Result
Top Left	Yes, all 1	Leaf
Top Right	No	Recurse
Bottom Left	Yes, all 1	Leaf
Bottom Right	Yes, all 0	Leaf

The top-right region must be subdivided again.

Its four 2 x 2 quadrants are:

Quadrant	Value
Top Left	0
Top Right	0
Bottom Left	1
Bottom Right	1

All are uniform, so they become leaf nodes.

The final tree therefore contains one internal root node and another internal node for the top-right quadrant.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n² log n)	Each recursive level scans matrix regions
Space	O(log n)	Recursive call stack depth

The recursion depth is logarithmic because each subdivision halves the side length.

The time complexity comes from repeatedly scanning regions to determine uniformity. In the worst case, many recursive calls occur and each level collectively examines much of the matrix again.

Since n <= 64, this complexity is easily acceptable.

Test Cases

# Helper function for testing
def is_leaf(node, val):
    return node.isLeaf and node.val == val

# Example 1
grid1 = [
    [0, 1],
    [1, 0]
]

root1 = Solution().construct(grid1)

assert root1.isLeaf is False  # root should be internal
assert is_leaf(root1.topLeft, False)  # top-left quadrant
assert is_leaf(root1.topRight, True)  # top-right quadrant
assert is_leaf(root1.bottomLeft, True)  # bottom-left quadrant
assert is_leaf(root1.bottomRight, False)  # bottom-right quadrant

# Example 2
grid2 = [
    [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]
]

root2 = Solution().construct(grid2)

assert root2.isLeaf is False  # root should be internal
assert root2.topLeft.isLeaf is True  # uniform quadrant
assert root2.topRight.isLeaf is False  # mixed quadrant

# Single cell with 0
grid3 = [[0]]

root3 = Solution().construct(grid3)

assert is_leaf(root3, False)  # smallest possible grid

# Single cell with 1
grid4 = [[1]]

root4 = Solution().construct(grid4)

assert is_leaf(root4, True)  # single-cell one

# Fully uniform grid
grid5 = [
    [1,1],
    [1,1]
]

root5 = Solution().construct(grid5)

assert root5.isLeaf is True  # should compress into one node
assert root5.val is True

# Checkerboard pattern
grid6 = [
    [0,1,0,1],
    [1,0,1,0],
    [0,1,0,1],
    [1,0,1,0]
]

root6 = Solution().construct(grid6)

assert root6.isLeaf is False  # forces maximum subdivision

# Large zero grid
grid7 = [
    [0,0,0,0],
    [0,0,0,0],
    [0,0,0,0],
    [0,0,0,0]
]

root7 = Solution().construct(grid7)

assert root7.isLeaf is True  # fully compressible
assert root7.val is False

Test	Why
Mixed 2x2 grid	Validates recursive subdivision
Complex 8x8 example	Validates multi-level recursion
Single cell 0	Smallest possible input
Single cell 1	Smallest positive leaf
Fully uniform grid	Ensures compression works
Checkerboard pattern	Forces maximum recursive depth
Large all-zero grid	Ensures large uniform regions compress correctly

Edge Cases

Single Cell Grid

A 1 x 1 matrix is the smallest valid input. This case is important because recursion must terminate correctly without attempting further subdivision.

The implementation handles this naturally because a single cell is always uniform. The recursive function immediately creates a leaf node.

Fully Uniform Matrix

A grid where every value is identical should produce exactly one leaf node rather than many smaller nodes.

A buggy implementation might continue subdividing unnecessarily. The uniformity scan prevents that by stopping recursion as soon as all values match.

For example:

[
 [1,1],
 [1,1]
]

produces a single leaf node.

Maximum Subdivision Pattern

A checkerboard pattern is the worst case for recursion because no larger region is uniform.

Example:

[
 [0,1],
 [1,0]
]

Every region larger than 1 x 1 must be subdivided. This stresses the recursive structure and verifies that quadrant coordinates are computed correctly.

The implementation handles this safely because every recursive call reduces the region size by half until single-cell regions are reached.