#427

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Construct Quad Tree

Construct a Quad-Tree from a binary matrix by recursively subdividing regions and tracking uniform states efficiently.

Problem Statement

Given an n x n binary matrix grid containing only 0's and 1's, represent the grid using a Quad-Tree. Each Quad-Tree node stores two attributes: val (True for 1, False for 0) and isLeaf (indicating if all values in the region are identical).

Return the root of the constructed Quad-Tree. Internal nodes must have exactly four children corresponding to top-left, top-right, bottom-left, and bottom-right sub-regions. Use recursive subdivision to track uniform regions and maintain the tree structure efficiently.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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

Example 2

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

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

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 3

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]]

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 == 2x where 0 <= x <= 6

Solution Approach

Check for uniform region

Examine the current sub-grid to see if all values are the same. If so, create a leaf node with val set accordingly and mark isLeaf as True. This prevents unnecessary recursion and ensures state tracking aligns with the Quad-Tree pattern.

Divide and conquer

If the sub-grid contains mixed values, split it into four equal quadrants. Recursively apply the same procedure to each quadrant. This maintains binary-tree traversal consistency and constructs internal nodes only when required, reducing redundant computations.

Combine child nodes

After processing four quadrants, combine the results into a parent node with isLeaf False. Assign topLeft, topRight, bottomLeft, and bottomRight children appropriately. This step consolidates tracked states and ensures the tree represents the original grid correctly.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of regions recursively subdivided; in the worst case it approaches O(n^2 log n) for maximum splits. Space complexity includes recursion stack and tree nodes, also roughly O(n^2) in the worst case.

What Interviewers Usually Probe

Expect candidate to identify uniform sub-grids and avoid unnecessary recursion.
Look for proper recursive subdivision of the grid into four quadrants per internal node.
Assess if the candidate correctly maintains node attributes val and isLeaf throughout traversal.

Common Pitfalls or Variants

Common pitfalls

Creating internal nodes for uniform regions instead of leaf nodes, increasing unnecessary tree size.
Failing to divide the grid properly into exactly four quadrants for each non-leaf node.
Ignoring tracking of uniform states leading to incorrect isLeaf assignments and wrong val values.

Follow-up variants

Construct Quad-Tree for larger matrices with varying sizes n = 2^x where 0 <= x <= 6.
Modify to compress sparse matrices where many 0's can be grouped to optimize space.
Extend to track additional metadata per node, such as counts of 1's and 0's, while maintaining traversal pattern.

FAQ

What is the easiest way to determine if a grid region forms a leaf node?

Check if all values in the current sub-grid are identical; if so, create a leaf node with val corresponding to that value and set isLeaf True.

How do you efficiently divide the grid for Quad-Tree construction?

Split the current grid region into four equal quadrants recursively, ensuring topLeft, topRight, bottomLeft, and bottomRight are processed systematically.

Why is state tracking important in Construct Quad Tree?

Tracking whether a region is uniform allows you to avoid unnecessary recursion and ensures the isLeaf and val attributes are accurate for each node.

Can this approach handle non-square matrices?

No, the Quad-Tree construction assumes n x n grids where n is a power of two, as per the problem constraints.

How does GhostInterview assist with binary-tree traversal in this problem?

It automatically applies the divide-and-conquer traversal while monitoring each node's uniformity, helping construct correct Quad-Tree structures efficiently.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

"""
# 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(a, b, c, d):
            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
            isLeaf = zero + one == 1
            val = isLeaf and one
            if isLeaf:
                return Node(grid[a][b], True)
            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)
            return Node(val, isLeaf, topLeft, topRight, bottomLeft, bottomRight)

        return dfs(0, 0, len(grid) - 1, len(grid[0]) - 1)

Continue Practicing

#240 search a 2d matrix ii #654 maximum binary tree #108 convert sorted array to binary search tree