LeetCode 427: Construct Quad Tree

Problem Restatement

We are given an n x n grid containing only 0 and 1.

We need to build a quad tree that represents this grid.

A quad tree is a tree where each internal node has exactly four children:

Each node has two main fields:

If a square region contains only 0s or only 1s, it becomes a leaf node.

If a square region contains both 0 and 1, we split it into four equal smaller squares and recursively build four child nodes.

For internal nodes, val can be either True or False; LeetCode accepts both. The important field for internal nodes is isLeaf = False.

Input and Output

The node structure is usually:

class Node:
    def __init__(
        self,
        val=False,
        isLeaf=False,
        topLeft=None,
        topRight=None,
        bottomLeft=None,
        bottomRight=None,
    ):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight

Examples

Consider this grid:

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

The whole grid has the same value, so the result is one leaf node:

Node(val=True, isLeaf=True)

No children are needed.

Now consider:

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

The whole grid is not uniform.

So we split it into four 1 x 1 regions:

topLeft     = 1
topRight    = 0
bottomLeft  = 0
bottomRight = 1

Each 1 x 1 region is uniform, so each child is a leaf node.

The root is an internal node:

Node(val=True, isLeaf=False)

with four children.

First Thought: Check Every Region Directly

For any square region, we can check whether all cells have the same value.

Suppose the region starts at row r, column c, and has side length size.

We compare every cell in that region against:

grid[r][c]

If every value is the same, we create a leaf node.

If at least one value differs, we split the region into four quadrants.

This is the natural recursive structure of the problem.

Key Insight

The grid itself is already a square that can be recursively divided into four smaller squares.

So the core function should mean:

build(r, c, size)

This builds the quad tree for the square region:

rows    r to r + size - 1
columns c to c + size - 1

For each call:

1. Check whether the current square is uniform.
2. If uniform, return a leaf node.
3. Otherwise, split into four smaller squares of size size // 2.
4. Return an internal node with those four children.

This avoids copying subgrids. We pass only coordinates and size.

Algorithm

Start with the full grid:

build(0, 0, len(grid))

Inside build(r, c, size):

Check whether all cells in the square have the same value as grid[r][c].

If yes:

return Node(grid[r][c] == 1, True)

Otherwise, compute:

half = size // 2

Build the four children:

topLeft = build(r, c, half)
topRight = build(r, c + half, half)
bottomLeft = build(r + half, c, half)
bottomRight = build(r + half, c + half, half)

Return an internal node:

return Node(
    True,
    False,
    topLeft,
    topRight,
    bottomLeft,
    bottomRight,
)

The value True for an internal node is arbitrary. LeetCode accepts either value when isLeaf is False.

Correctness

We prove the algorithm constructs the correct quad tree for every square region.

For a uniform region, all cells have the same value. The quad tree rule says such a region should be represented by one leaf node with isLeaf = True and val equal to that value. The algorithm checks all cells in the region and returns exactly that node.

For a non-uniform region, the quad tree rule says the region must be split into four equal quadrants. The algorithm computes half = size // 2 and recursively builds the four required child regions: top-left, top-right, bottom-left, and bottom-right.

Each recursive call constructs the correct quad tree for its own smaller region by the same rule. The parent node then stores those four child trees and marks itself as an internal node with isLeaf = False.

The initial call covers the whole grid. Therefore, the returned root represents the entire input grid correctly.

Complexity

The output tree itself can contain many nodes. The table counts extra working space, excluding the returned tree.

In the worst case, many regions are non-uniform, so the algorithm scans cells repeatedly across multiple recursion levels.

Implementation

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

        def is_uniform(r: int, c: int, size: int) -> bool:
            first = grid[r][c]

            for i in range(r, r + size):
                for j in range(c, c + size):
                    if grid[i][j] != first:
                        return False

            return True

        def build(r: int, c: int, size: int) -> 'Node':
            if is_uniform(r, c, size):
                return Node(grid[r][c] == 1, True)

            half = size // 2

            top_left = build(r, c, half)
            top_right = build(r, c + half, half)
            bottom_left = build(r + half, c, half)
            bottom_right = build(r + half, c + half, half)

            return Node(
                True,
                False,
                top_left,
                top_right,
                bottom_left,
                bottom_right,
            )

        return build(0, 0, n)

Code Explanation

The public method starts with the full grid size:

n = len(grid)

The helper is_uniform checks whether a square region contains only one value.

first = grid[r][c]

This is the value every other cell must match.

The nested loops scan all cells inside the square:

for i in range(r, r + size):
    for j in range(c, c + size):

If any value differs, the region needs to be split:

if grid[i][j] != first:
    return False

The recursive function build constructs a quad tree node for one square region.

If the region is uniform, we return a leaf:

return Node(grid[r][c] == 1, True)

The value must be boolean, so grid[r][c] == 1 converts 1 to True and 0 to False.

If the region is not uniform, we split it:

half = size // 2

Then we build each quadrant with the correct coordinates.

Top-left keeps the same starting point:

build(r, c, half)

Top-right starts half columns to the right:

build(r, c + half, half)

Bottom-left starts half rows below:

build(r + half, c, half)

Bottom-right moves both down and right:

build(r + half, c + half, half)

The returned internal node has isLeaf = False.

return Node(True, False, top_left, top_right, bottom_left, bottom_right)

The val field is set to True, but for internal nodes that value does not matter.

Testing

We can test by serializing the tree into a simple nested tuple format.

class Node:
    def __init__(
        self,
        val=False,
        isLeaf=False,
        topLeft=None,
        topRight=None,
        bottomLeft=None,
        bottomRight=None,
    ):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight

def serialize(root):
    if root.isLeaf:
        return ("leaf", root.val)

    return (
        "node",
        serialize(root.topLeft),
        serialize(root.topRight),
        serialize(root.bottomLeft),
        serialize(root.bottomRight),
    )

def run_tests():
    s = Solution()

    root = s.construct([
        [1, 1],
        [1, 1],
    ])
    assert serialize(root) == ("leaf", True)

    root = s.construct([
        [0, 0],
        [0, 0],
    ])
    assert serialize(root) == ("leaf", False)

    root = s.construct([
        [1, 0],
        [0, 1],
    ])
    assert serialize(root) == (
        "node",
        ("leaf", True),
        ("leaf", False),
        ("leaf", False),
        ("leaf", True),
    )

    root = s.construct([
        [1],
    ])
    assert serialize(root) == ("leaf", True)

    print("all tests passed")

run_tests()

Test meaning: