Abstract / Summary

Build a quadtree from a grid by recursively dividing into four and checking if each section is uniform.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 79% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Divide And Conquer
• Matrix
• Tree

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation builds a quad-tree representation of a square binary matrix. The construct method receives a two-dimensional list grid whose side length is a power of two. It computes the height of the tree from the matrix size, then recursively partitions the matrix into four equal quadrants until reaching individual cells. At each recursion level the function decides whether the four child nodes can be merged into a single leaf node; otherwise it creates an internal node that references the four children.

Key Steps

Determining the tree height

size = len(grid)
height = int(log2(size))

The side length of the matrix is stored in size. Because the matrix size is guaranteed to be a power of two, taking the base-2 logarithm yields the number of subdivision levels required to reach single cells. The result is stored in height and passed to the recursive builder.

Recursive construction function

def build(x, y, level):
    if level == 0:
        return Node(grid[y][x], True, None, None, None, None)

    step = 2**(level - 1)
    a = build(x,      y,      level-1)
    b = build(x+step, y,      level-1)
    c = build(x,      y+step, level-1)
    d = build(x+step, y+step, level-1)
    if a.isLeaf and b.isLeaf and c.isLeaf and d.isLeaf and a.val == b.val and b.val == c.val and c.val == d.val:
        return Node(a.val, True, None, None, None, None)
    else:
        return Node(a.val, False, a, b, c, d)

The function build receives the top-left coordinates (x, y) of the current sub-grid and the remaining level count. When level reaches zero the sub-grid corresponds to a single matrix element; a leaf node is created directly from that value.

For higher levels the side length of the current sub-grid is 2**level. The variable step equals half of that length, allowing the function to compute the origins of the four quadrants: top-left (a), top-right (b), bottom-left (c), and bottom-right (d). Each quadrant is processed by a recursive call with level-1.

After the four child nodes are obtained, the code checks whether all four are leaves and share the same boolean value. If that condition holds, the four leaves are collapsed into a single leaf node whose value matches the children. Otherwise an internal node is created; its isLeaf flag is set to False and it stores references to the four child nodes. The value stored in an internal node is taken from the first child (a.val), which is permissible because the value field is irrelevant for non-leaf nodes.

Initiating the recursion

return build(0, 0, height)

The construction starts at the origin of the matrix with the full height, producing the root of the quad-tree.

Edge Cases Handled

When the input matrix consists of a single element (size == 1), height becomes zero. The recursive call build(0, 0, 0) immediately triggers the base case, returning a leaf node that directly reflects the sole matrix value. This path avoids any further subdivision and correctly represents the trivial quad-tree.

If an entire quadrant contains uniform values, the recursive descent still creates leaf nodes for each cell, but the subsequent merging condition collapses them into a single leaf node for that quadrant. This behavior ensures that large homogeneous regions are represented compactly, regardless of their position in the matrix.

The algorithm also gracefully handles matrices where uniformity appears only at deeper levels. For example, a quadrant may consist of a mixture of values that only become uniform after further subdivision; the recursion continues until the base case, then merges only when the four children satisfy the uniformity test. This guarantees correct representation of any pattern of 0s and 1s.

Performance Optimizations

The recursion computes the size of each quadrant using step = 2**(level - 1). Because the exponentiation is performed with integer powers of two, the operation is effectively a bit shift, which is computationally cheap. The algorithm avoids recomputing the size of sub-grids from coordinates; it derives the step directly from the current recursion depth.

Merging of homogeneous leaf nodes reduces the total number of nodes created. Instead of constructing a full tree with 4^height leaf nodes, the code collapses any region where all four children are identical into a single node. This pruning dramatically cuts memory usage for matrices with large uniform blocks.

The base case returns a node without allocating child references (None for all four pointers). This minimizes the memory footprint for leaf nodes, as they do not carry unnecessary references.

All recursive calls are tail-independent; each call creates exactly four child calls and then decides on merging. The recursion depth equals the height of the tree, which is log2(size). Consequently, the call stack grows only proportionally to the logarithm of the matrix dimension, keeping stack usage modest even for large inputs.

Imagine you have a big square puzzle made of many tiny colored blocks. This computer code acts like a very smart puzzle maker that tries to pack the picture into the smallest box possible. It starts by looking at the whole big square and asking if every single block inside is the exact same color. If all the blocks match, it just uses one big piece to represent the whole area. If the blocks are a mix of colors, it cuts the big square into four smaller equal squares. Then it runs the exact same rule on those smaller squares, checking if they can be individual solid colors or if they need to be cut again. It keeps doing this over and over until every part of the big puzzle is neatly packed using either one solid piece or a group of four smaller pieces. This is a clever way to save space while still remembering exactly what the original picture looks like.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Java	C++			Python		TS
	WalkCCC	Java	C++			Python
	leetcode.ca	Java	C++			Python	Go
	LeetcodeHelp	Java	C++			Python
	Progiez	Java	C++			Python
github	BigEggStudy				C#
	black-shadows		C++
	charles-wangkai	Java
	everthis			JS
	fsq		C++
	JoshCrozier			JS
	lkwq007					Python
	suxrobGM				C#
	varunu28	Java
	vthwang	Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
varunu28	Java
vthwang	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality