LeetCode Solutions Blog

Construct Quad Tree

Number: 772

Difficulty: Medium

Paid? No

Problem Description

Given an n x n matrix grid that contains only 0's and 1's, construct a Quad-Tree representation of the grid. Each node in the Quad-Tree either represents a region with all 0's or all 1's (a leaf node) or is an internal node with exactly four children representing the four quadrants of the grid.

Key Insights

Use a divide and conquer approach: recursively check if the current grid region is uniform.
A region is uniform if all entries are the same; if so, create a leaf node.
If not uniform, split the region into four equal quadrants and recursively construct the Quad-Tree for each.
Careful handling of grid boundaries is required during recursion.

Space and Time Complexity

Time Complexity: O(n^2) in the worst-case scenario since every cell might be inspected. Space Complexity: O(n^2) in the worst-case due to recursion stack and node storage.

Solution

We use recursion to examine each sub-grid of the matrix. First, we check if the current grid region has a uniform value. If it does, we return a leaf node with that value. If not, we partition the grid into four smaller quadrants (topLeft, topRight, bottomLeft, bottomRight) and recursively construct the corresponding Quad-Tree nodes for each quadrant. Finally, we create an internal node combining these four children. This strategy guarantees we process all parts of the grid and correctly form the Quad-Tree.

Code Solutions

# Definition for a Quad-Tree Node.
class Node:
    def __init__(self, val, isLeaf, topLeft=None, topRight=None, bottomLeft=None, bottomRight=None):
        self.val = val              # True for 1, False for 0.
        self.isLeaf = isLeaf        # Boolean indicating if this node is a leaf.
        self.topLeft = topLeft      # Child node for the top-left quadrant.
        self.topRight = topRight    # Child node for the top-right quadrant.
        self.bottomLeft = bottomLeft  # Child node for the bottom-left quadrant.
        self.bottomRight = bottomRight  # Child node for the bottom-right quadrant.

def construct(grid):
    # Helper function to determine if the current grid section is uniform.
    def is_uniform(r0, c0, length):
        value = grid[r0][c0]
        for i in range(r0, r0 + length):
            for j in range(c0, c0 + length):
                if grid[i][j] != value:
                    return False, value
        return True, value

    # Recursive function to build the Quad Tree.
    def helper(r0, c0, length):
        uniform, value = is_uniform(r0, c0, length)
        if uniform:
            # All cells are the same: create a leaf node.
            return Node(val=(value == 1), isLeaf=True)
        else:
            half = length // 2
            # Recursively construct each quadrant.
            topLeft = helper(r0, c0, half)
            topRight = helper(r0, c0 + half, half)
            bottomLeft = helper(r0 + half, c0, half)
            bottomRight = helper(r0 + half, c0 + half, half)
            # Create an internal node with four children.
            return Node(val=True, isLeaf=False, topLeft=topLeft, topRight=topRight,
                        bottomLeft=bottomLeft, bottomRight=bottomRight)

    n = len(grid)
    return helper(0, 0, n)