427. Construct Quad Tree - Explanation

Problem Link

Description

Given a n * n matrix grid of 0's and 1's only. We want to represent grid with a Quad-Tree.

Return the root of the Quad-Tree representing grid.

A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:

  • val: True if the node represents a grid of 1's or False if the node represents a grid of 0's. Notice that you can assign the val to True or False when isLeaf is False, and both are accepted in the answer.

  • isLeaf: True if the node is a leaf node on the tree or False if the node has four children.

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;
}

We can construct a Quad-Tree from a two-dimensional area using the following steps:

  1. If the current grid has the same value (i.e all 1's or all 0's) set isLeaf True and set val to the value of the grid and set the four children to Null and stop.

  2. If the current grid has different values, set isLeaf to False and set val to any value and divide the current grid into four sub-grids as shown in the photo.

  3. Recurse for each of the children with the proper sub-grid.

If you want to know more about the Quad-Tree, you can refer to the wiki.

Quad-Tree format:

You don't need to read this section for solving the problem. This is only if you want to understand the output format here. The output represents the serialized format of a Quad-Tree using level order traversal, where null signifies a path terminator where no node exists below.

It is very similar to the serialization of the binary tree. The only difference is that the node is represented as a list [isLeaf, val].

If the value of isLeaf or val is True we represent it as 1 in the list [isLeaf, val] and if the value of isLeaf or val is False we represent it as 0.


Example 1:

Input: grid = [[0,1],[1,0]]

Output: [[0,1],[1,0],[1,1],[1,1],[1,0]]

Explanation: The explanation of this example is shown below:
Notice that 0 represents False and 1 represents True in the photo representing the Quad-Tree.

Example 2:

Input: grid = [[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]]

Output: [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]

Explanation: All values in the grid are not the same. We divide the grid into four sub-grids.
The topLeft, bottomLeft and bottomRight each has the same value.
The topRight have different values so we divide it into 4 sub-grids where each has the same value.
Explanation is shown in the photo below:


Constraints:

  • n == grid.length == grid[i].length
  • n == 2ˣ where 0 <= x <= 6


Topics

Array Divide and Conquer Tree Matrix

Company Tags

Please upgrade to NeetCode Pro to view company tags.



Prerequisites

Before attempting this problem, you should be comfortable with:

  • Recursion / Divide and Conquer - Recursively dividing a grid into four equal quadrants
  • 2D Arrays / Matrices - Working with grid coordinates and subregion boundaries
  • Tree Data Structures - Understanding quad trees where each node has exactly four children

1. Recursion

Intuition

A quad tree recursively divides a 2D grid into four quadrants. If all values in a region are the same, that region becomes a leaf node. Otherwise, we split it into four equal parts and recursively build the tree. For each region, we first check if all cells have the same value; if so, we create a leaf node.

Algorithm

  1. Define dfs(n, r, c) where n is the size of the current region and (r, c) is its top-left corner.
  2. Check if all cells in the n x n region starting at (r, c) have the same value.
  3. If all values are the same, return a leaf node with that value.
  4. Otherwise, divide n by 2 and recursively build four children:
    • topLeft: dfs(n/2, r, c)
    • topRight: dfs(n/2, r, c + n/2)
    • bottomLeft: dfs(n/2, r + n/2, c)
    • bottomRight: dfs(n/2, r + n/2, c + n/2)
  5. Return a non-leaf node with these four children.
"""
# 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':
        def dfs(n, r, c):
            allSame = True
            for i in range(n):
                for j in range(n):
                    if grid[r][c] != grid[r + i][c + j]:
                        allSame = False
                        break
            if allSame:
                return Node(grid[r][c], True)

            n = n // 2
            topleft = dfs(n, r, c)
            topright = dfs(n, r, c + n)
            bottomleft = dfs(n, r + n, c)
            bottomright = dfs(n, r + n, c + n)

            return Node(0, False, topleft, topright, bottomleft, bottomright)

        return dfs(len(grid), 0, 0)

Time & Space Complexity

  • Time complexity: O(n2log⁡n)O(n ^ 2 \log n)
  • Space complexity: O(log⁡n)O(\log n) for recursion stack.

2. Recursion (Optimal)

Intuition

Instead of checking uniformity before recursing, we can recurse first and check uniformity after. If we reach a single cell, it is always a leaf. For larger regions, we build all four children first, then check if they are all leaves with the same value. If so, we can merge them into a single leaf node, avoiding the O(n^2) check at each level.

Algorithm

  1. Define dfs(n, r, c) where n is the region size and (r, c) is its top-left corner.
  2. Base case: if n == 1, return a leaf node with grid[r][c].
  3. Recursively build the four quadrants with size n / 2.
  4. If all four children are leaves and have the same value, return a single leaf with that value (merge them).
  5. Otherwise, return a non-leaf node with the four children.
"""
# 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':
        def dfs(n, r, c):
            if n == 1:
                return Node(grid[r][c] == 1, True)

            mid = n // 2
            topLeft = dfs(mid, r, c)
            topRight = dfs(mid, r, c + mid)
            bottomLeft = dfs(mid, r + mid, c)
            bottomRight = dfs(mid, r + mid, c + mid)

            if (topLeft.isLeaf and topRight.isLeaf and
                bottomLeft.isLeaf and bottomRight.isLeaf and
                topLeft.val == topRight.val == bottomLeft.val == bottomRight.val):
                return Node(topLeft.val, True)

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

        return dfs(len(grid), 0, 0)

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity: O(log⁡n)O(\log n) for recursion stack.

3. Recursion (Space Optimized)

Intuition

We can optimize memory by reusing leaf nodes. Since all leaves with value true are identical and all leaves with value false are identical, we can create just two singleton leaf nodes and reuse them throughout the tree instead of creating new leaf nodes each time.

Algorithm

  1. Create two shared leaf nodes: one for false and one for true.
  2. Define dfs(n, r, c) as before.
  3. Base case: if n == 1, return the appropriate shared leaf node based on grid[r][c].
  4. Recursively build the four quadrants.
  5. If all four children are leaves with the same value, return one of the children (they point to the same shared node).
  6. Otherwise, return a new non-leaf node with the four children.
"""
# 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':
        leafNodes = {
            0: Node(False, True),
            1: Node(True, True)
        }

        def dfs(n, r, c):
            if n == 1:
                return leafNodes[grid[r][c]]

            n //= 2
            topLeft = dfs(n, r, c)
            topRight = dfs(n, r, c + n)
            bottomLeft = dfs(n, r + n, c)
            bottomRight = dfs(n, r + n, c + n)

            if (topLeft.isLeaf and topRight.isLeaf and
                bottomLeft.isLeaf and bottomRight.isLeaf and
                topLeft.val == topRight.val == bottomLeft.val == bottomRight.val):
                return topLeft

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

        return dfs(len(grid), 0, 0)

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity: O(log⁡n)O(\log n) for recursion stack.

Common Pitfalls

Confusing Row and Column Offsets When Dividing Quadrants

When dividing the grid into four quadrants, the top-left stays at (r, c), but the other three quadrants need correct offsets. A common mistake is swapping row and column increments.

# Wrong: Incorrect quadrant positions
topRight = dfs(n//2, r + n//2, c)  # Should be (r, c + n//2)
bottomLeft = dfs(n//2, r, c + n//2)  # Should be (r + n//2, c)

Forgetting to Check All Four Children Are Leaves Before Merging

When merging four children into a single leaf node, you must verify that all four children are leaves AND have the same value. Checking only the values without confirming they are leaves will incorrectly merge non-leaf nodes.

# Wrong: Only checking values
if topLeft.val == topRight.val == bottomLeft.val == bottomRight.val:
    return Node(topLeft.val, True)

# Correct: Check isLeaf AND values
if (topLeft.isLeaf and topRight.isLeaf and
    bottomLeft.isLeaf and bottomRight.isLeaf and
    topLeft.val == topRight.val == bottomLeft.val == bottomRight.val):
    return Node(topLeft.val, True)

Using Wrong Grid Size for Recursion

When dividing the grid, the new size should be n // 2, not n - 1 or any other calculation. Each level of recursion should exactly halve the region size since the grid dimension is always a power of 2.