427. Construct Quad Tree - Explanation

Problem Link

Description

You are given a n * n binary matrix grid. 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:

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

  • val: True if the node represents a grid cell of 1's or False if the node represents a grid cell 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.

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 grid 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 representing the four childrens of the current node.

  3. Recurse the steps for every children of the current node.

Example 1:

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

Output: [[1,1]]

Example 2:

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

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

Constraints:

  • n == grid.length == grid[i].length
  • n == (2^x) where 0 <= x <= 6


Company Tags

Please upgrade to NeetCode Pro to view company tags.



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.