Problem Description

This problem asks you to construct a Quad-Tree from a given n × n binary matrix (containing only 0s and 1s).

A Quad-Tree is a tree data structure where each internal node has exactly four children representing the four quadrants: top-left, top-right, bottom-left, and bottom-right. Each node in the tree has two properties:

• val: A boolean value (True for 1s, False for 0s)
• isLeaf: A boolean indicating whether the node is a leaf (True) or has four children (False)

The construction follows these rules:

1. If a region contains all the same values (all 0s or all 1s):

   • Create a leaf node with isLeaf = True
   • Set val to the grid's value (True for 1, False for 0)
   • The four children are set to null

2. If a region contains mixed values (both 0s and 1s):

   • Create an internal node with isLeaf = False
   • Set val to any value (it doesn't matter since it's not a leaf)
   • Divide the current region into four equal quadrants
   • Recursively construct four children nodes for each quadrant

The solution uses a recursive divide-and-conquer approach. The dfs function takes the boundaries of a rectangular region (a, b) to (c, d) and:

1. Checks if all values in the region are the same
2. If yes, creates a leaf node
3. If no, divides the region into four quadrants and recursively builds child nodes

The key insight is finding the midpoints to split the grid: ((a+c)//2, (b+d)//2) divides the region into four equal parts, and the function recursively processes each quadrant to build the complete Quad-Tree structure.

Intuition

The natural way to think about this problem is to recognize that a Quad-Tree is inherently a recursive structure - each node either represents a uniform region (leaf) or contains four smaller Quad-Trees as children. This immediately suggests a divide-and-conquer approach.

When we look at any square region in the grid, we face a decision: Is this region uniform (all 0s or all 1s), or does it contain mixed values? If it's uniform, we've found a leaf node and can stop dividing. If it's mixed, we need to break it down further.

The key insight is that we can treat any square sub-region of the grid the same way we treat the entire grid. This recursive property means we can:

1. Start with the entire grid
2. Check if it's uniform
3. If not, split it into four equal quadrants
4. Apply the same logic to each quadrant

The splitting pattern follows the natural quadrant division: we find the midpoint of our current region and use it to create four smaller squares. For a region from (a, b) to (c, d), the midpoint is ((a+c)//2, (b+d)//2). This gives us:

• Top-left: from (a, b) to (mid_row, mid_col)
• Top-right: from (a, mid_col+1) to (mid_row, d)
• Bottom-left: from (mid_row+1, b) to (c, mid_col)
• Bottom-right: from (mid_row+1, mid_col+1) to (c, d)

The recursion naturally handles the tree construction: when we determine a region needs to be split, we create a non-leaf node and let the recursive calls build its four children. The base case (uniform region) creates leaf nodes, ensuring the recursion terminates. This bottom-up construction perfectly mirrors the top-down division of the grid, making the solution both elegant and efficient.

Solution Approach

The implementation uses a recursive depth-first search (DFS) approach to construct the Quad-Tree. Here's how the solution works step by step:

Main Function Structure: The construct method initializes the recursive process by calling dfs(0, 0, len(grid) - 1, len(grid[0]) - 1), which processes the entire grid from top-left corner (0, 0) to bottom-right corner (n-1, n-1).

The DFS Helper Function: The dfs(a, b, c, d) function takes four parameters representing a rectangular region:

• (a, b): top-left corner coordinates
• (c, d): bottom-right corner coordinates

Step 1: Check Region Uniformity

zero = one = 0
for i in range(a, c + 1):
    for j in range(b, d + 1):
        if grid[i][j] == 0:
            zero = 1
        else:
            one = 1

The function scans the entire region to determine if it contains zeros, ones, or both. Instead of counting all occurrences, it uses binary flags (zero and one) to track presence, which is more efficient.

Step 2: Determine Leaf Status

isLeaf = zero + one == 1
val = isLeaf and one

If zero + one == 1, the region is uniform (contains only 0s or only 1s), making it a leaf node. The val is set to True if the region contains only 1s.

Step 3: Handle Leaf Nodes

if isLeaf:
    return Node(grid[a][b], True)

For uniform regions, create and return a leaf node. Since all values are the same, grid[a][b] represents the entire region's value.

Step 4: Handle Non-Leaf Nodes (Divide and Conquer) For mixed regions, calculate the midpoints and recursively construct four quadrants:

topLeft = dfs(a, b, (a + c) // 2, (b + d) // 2)
topRight = dfs(a, (b + d) // 2 + 1, (a + c) // 2, d)
bottomLeft = dfs((a + c) // 2 + 1, b, c, (b + d) // 2)
bottomRight = dfs((a + c) // 2 + 1, (b + d) // 2 + 1, c, d)

The midpoint calculations (a + c) // 2 and (b + d) // 2 split the region into four equal parts. Each recursive call processes one quadrant and returns its corresponding node.

Step 5: Construct Internal Node

return Node(val, isLeaf, topLeft, topRight, bottomLeft, bottomRight)

Finally, create and return an internal node with the four children obtained from recursive calls. The val for non-leaf nodes can be any value (here it's False from the earlier calculation), and isLeaf is False.

Time Complexity: O(n² log n) in the worst case, where we need to check every cell and the tree has maximum depth. Space Complexity: O(log n) for the recursion stack depth, plus O(n²) for the Quad-Tree nodes in the worst case.

Example Walkthrough

Let's walk through constructing a Quad-Tree for a 4×4 binary matrix:

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

Initial Call: dfs(0, 0, 3, 3) - Process entire 4×4 grid

Step 1: Check if the entire grid is uniform

• Scanning all cells: found both 0s and 1s
• Not uniform → Need to split into quadrants

Step 2: Calculate midpoints

• Row midpoint: (0 + 3) // 2 = 1
• Column midpoint: (0 + 3) // 2 = 1

Step 3: Recursively process four quadrants

Quadrant 1 - Top-Left: dfs(0, 0, 1, 1)

[1,1]
[1,1]

• All values are 1 → Create leaf node with val=True

Quadrant 2 - Top-Right: dfs(0, 2, 1, 3)

[0,0]
[0,0]

• All values are 0 → Create leaf node with val=False

Quadrant 3 - Bottom-Left: dfs(2, 0, 3, 1)

[1,1]
[1,1]

• All values are 1 → Create leaf node with val=True

Quadrant 4 - Bottom-Right: dfs(2, 2, 3, 3)

[1,1]
[1,1]

• All values are 1 → Create leaf node with val=True

Step 4: Create root node

• Create internal node with isLeaf=False
• Attach the four leaf nodes as children

Final Quad-Tree Structure:

        Root (isLeaf=False)
       /    |     |      \
      /     |     |       \
  TL(1)   TR(0)  BL(1)   BR(1)
(leaf)   (leaf) (leaf)   (leaf)

Each leaf represents a 2×2 uniform region, and the root connects them together. The tree efficiently represents the original 4×4 grid with just 5 nodes instead of 16 individual cells.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n² × log n) where n is the side length of the grid.

The analysis breaks down as follows:

• In the worst case, the quadtree needs to be fully constructed when no regions can be merged into leaves
• The recursion depth is log n (since we divide the grid into quarters at each level)
• At each level k of the recursion tree, there are 4^k subproblems
• Each subproblem at level k processes a grid of size (n/2^k) × (n/2^k) = n²/4^k elements
• Total work at level k: 4^k × n²/4^k = n²
• Since there are log n levels, total time complexity is O(n² × log n)

Alternatively, we can view it as:

• Each cell in the n × n grid can be visited multiple times during the recursion
• In the worst case, a cell is visited O(log n) times (once at each level of recursion it belongs to)
• Total: O(n² × log n)

Space Complexity: O(n²)

The space complexity consists of:

• Recursion stack: O(log n) - The maximum depth of recursion is log n when dividing the grid into quarters
• QuadTree nodes: O(n²) - In the worst case where no merging is possible, we create O(n²) nodes (approximately (4^(log n) - 1)/3 = (n² - 1)/3 internal nodes plus leaf nodes)
• The dominant factor is the space for storing the quadtree nodes, giving us O(n²) total space complexity

Common Pitfalls

1. Incorrect Quadrant Boundary Calculation

One of the most common mistakes is incorrectly calculating the boundaries when dividing the region into four quadrants. Developers often make off-by-one errors when determining where each quadrant starts and ends.

Incorrect Example:

# Wrong: Missing +1 for bottom and right quadrants
topLeft = dfs(a, b, (a + c) // 2, (b + d) // 2)
topRight = dfs(a, (b + d) // 2, (a + c) // 2, d)  # Missing +1
bottomLeft = dfs((a + c) // 2, b, c, (b + d) // 2)  # Missing +1
bottomRight = dfs((a + c) // 2, (b + d) // 2, c, d)  # Missing +1 twice

Correct Solution:

mid_row = (row_start + row_end) // 2
mid_col = (col_start + col_end) // 2

topLeft = dfs(row_start, col_start, mid_row, mid_col)
topRight = dfs(row_start, mid_col + 1, mid_row, col_end)
bottomLeft = dfs(mid_row + 1, col_start, row_end, mid_col)
bottomRight = dfs(mid_row + 1, mid_col + 1, row_end, col_end)

2. Confusing Node Value for Non-Leaf Nodes

Many developers mistakenly think they need to calculate a meaningful value for non-leaf nodes, leading to unnecessary complexity.

Incorrect Approach:

if not is_leaf:
    # Unnecessarily complex - trying to determine a "representative" value
    val = grid[(row_start + row_end) // 2][(col_start + col_end) // 2]
    # Or worse, trying to compute majority value
    val = count_ones > count_zeros

Correct Solution: For non-leaf nodes, the val field is irrelevant and can be set to any value (True, False, 0, or 1):

return Node(val=True, isLeaf=False, ...)  # val can be any value

3. Inefficient Region Uniformity Check

Counting all occurrences when you only need to know if the region is uniform wastes time.

Inefficient Example:

# Unnecessarily counting all values
count_zeros = 0
count_ones = 0
for i in range(row_start, row_end + 1):
    for j in range(col_start, col_end + 1):
        if grid[i][j] == 0:
            count_zeros += 1
        else:
            count_ones += 1

is_leaf = (count_zeros == 0) or (count_ones == 0)

Efficient Solution: Use boolean flags and early termination:

has_zero = has_one = False
for row in range(row_start, row_end + 1):
    for col in range(col_start, col_end + 1):
        if grid[row][col] == 0:
            has_zero = True
        else:
            has_one = True
        # Early exit when both values found
        if has_zero and has_one:
            return Node(True, False, ...)  # Not a leaf

4. Incorrect Base Case for Single Cell

Forgetting to handle the base case when the region is a single cell (row_start == row_end and col_start == col_end).

Potential Issue:

# May cause infinite recursion if not handled properly
def dfs(row_start, col_start, row_end, col_end):
    # Missing explicit base case check
    mid_row = (row_start + row_end) // 2  # When equal, this equals row_start
    mid_col = (col_start + col_end) // 2  # When equal, this equals col_start
    # Recursive calls with same parameters → infinite recursion

Solution: The uniformity check naturally handles single cells, but being explicit improves clarity:

# Single cell is always uniform and thus a leaf
if row_start == row_end and col_start == col_end:
    return Node(grid[row_start][col_start], True, None, None, None, None)

5. Misunderstanding Grid Dimensions

Assuming the grid is always square or that N must be a power of 2 in the implementation (though the problem states this, defensive coding is good practice).

Better Practice:

def construct(self, grid: List[List[int]]) -> 'Node':
    if not grid or not grid[0]:
        return None
  
    n = len(grid)
    # Verify square matrix if needed
    assert all(len(row) == n for row in grid), "Grid must be square"
  
    return build_quadtree(0, 0, n - 1, n - 1)