LeetCode 427: Construct Quad Tree Solution in Python – A Step-by-Step Guide

What Is LeetCode 427: Construct Quad Tree?

In LeetCode 427: Construct Quad Tree, you’re given an n × n binary grid (e.g., [[1,1,1,1],[1,1,1,1],[0,0,0,0],[0,0,0,0]]), where each cell is 0 or 1, and you need to construct a Quad Tree representing it. A Quad Tree is a tree where each node is either:

• A leaf (all values in its region are the same, isLeaf = True, val = 0 or 1).
• A non-leaf (split into four quadrants: top-left, top-right, bottom-left, bottom-right, isLeaf = False).

The root represents the entire grid, and you recursively divide until each region is uniform. For the example, the root splits into four 2×2 leaves: all 1s, all 1s, all 0s, all 0s. You return the root Node of the Quad Tree.

Problem Statement

• Input: An n × n integer grid (0s and 1s).
• Output: A Node object—the root of the Quad Tree.
• Rules:
• Leaf if all values in region are same (isLeaf = True, val = value).
• Non-leaf splits into four children (top-left, top-right, bottom-left, bottom-right).
• n is a power of 2.

Constraints

• n == grid.length == grid[i].length.
• n is a power of 2, 1 <= n <= 64.
• grid[i][j] is 0 or 1.

Examples

• Input: grid = [[0,1],[1,0]]
• Output: Node(isLeaf=False, val=None, topLeft=Node(0), topRight=Node(1), bottomLeft=Node(1), bottomRight=Node(0)).
• Input: grid = [[1,1,1,1],[1,1,1,1],[0,0,0,0],[0,0,0,0]]
• Output: Node(isLeaf=False, val=None, topLeft=Node(1), topRight=Node(1), bottomLeft=Node(0), bottomRight=Node(0)).
• Input: grid = [[1]]
• Output: Node(isLeaf=True, val=1).

Understanding the Problem: Building the Quad Tree

To solve LeetCode 427: Construct Quad Tree in Python, we need to transform an n × n binary grid into a Quad Tree by recursively splitting it into four quadrants until each region is uniform (all 0s or all 1s). A naive idea might be to check every cell and build bottom-up—but we can use the grid’s structure smarter! We’ll use:

• Best Solution (Recursive Divide-and-Conquer): O(n² * log n) time, O(log n) space—splits efficiently.
• Alternative Solution (Iterative with Matrix Traversal): O(n² * log n) time, O(n²) space—processes level-by-level.

Let’s dive into the recursive solution with a clear, step-by-step explanation.

Best Solution: Recursive Divide-and-Conquer

Why This Is the Best Solution

The recursive divide-and-conquer method is the top pick because it’s efficient—O(n² * log n) time, O(log n) space (recursion stack)—and naturally fits the Quad Tree’s hierarchical structure. It checks if a region is uniform; if not, it splits into four quadrants and recurses, building the tree top-down. It’s like chopping a big map into smaller pieces until each is a solid color!

How It Works

Think of the grid as a map you’re dividing:

• Step 1: Check Uniformity:
• For a region (x, y, size), scan all cells.
• If all match first cell’s value, return a leaf node.
• Step 2: Split and Recurse:
• If not uniform, divide into four quadrants:
• Top-left: (x, y, size/2).
• Top-right: (x, y + size/2, size/2).
• Bottom-left: (x + size/2, y, size/2).
• Bottom-right: (x + size/2, y + size/2, size/2).
• Recurse on each quadrant.
• Step 3: Build Node:
• Non-leaf: isLeaf = False, set four children.
• Leaf: isLeaf = True, val = cell value.
• Step 4: Why This Works:
• Recursion ensures every region is processed.
• In-place grid access, minimal space beyond stack.
• It’s like slicing a puzzle into matching pieces!

Step-by-Step Example

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

• Grid (4×4):

1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0

• Root (0, 0, 4):
• Check: 1s and 0s, not uniform.
• Split:
• Top-Left (0, 0, 2):

Copy code  ```
  1 1
  1 1
  ```

• All 1s, leaf: Node(True, 1).

1 1 1 1

• All 1s, leaf: Node(True, 1).

0 0 0 0

• All 0s, leaf: Node(True, 0).

0 0 0 0

• All 0s, leaf: Node(True, 0).

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

• Root (0, 0, 2):
• Not uniform, split:
• TL (0, 0, 1): 0, leaf.
• TR (0, 1, 1): 1, leaf.
• BL (1, 0, 1): 1, leaf.
• BR (1, 1, 1): 0, leaf.
• Root: Node(False, None, TL=0, TR=1, BL=1, BR=0).
• Result: Root with four leaves.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy code# 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':
        if not grid:
            return None

        # Step 1: Recursive helper function
        def build(x, y, size):
            # Check if region is uniform
            val = grid[x][y]
            uniform = True
            for i in range(x, x + size):
                for j in range(y, y + size):
                    if grid[i][j] != val:
                        uniform = False
                        break
                if not uniform:
                    break

            # Step 2: If uniform, return leaf
            if uniform:
                return Node(val, True, None, None, None, None)

            # Step 3: Split and recurse
            half = size // 2
            topLeft = build(x, y, half)
            topRight = build(x, y + half, half)
            bottomLeft = build(x + half, y, half)
            bottomRight = build(x + half, y + half, half)

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

        # Step 4: Start with full grid
        return build(0, 0, len(grid))

• Line 2-10: Node class (given):
• val, isLeaf, four child pointers (topLeft, topRight, bottomLeft, bottomRight).
• Line 14-16: Handle empty grid, return None.
• Line 19-38: Build function:
• Line 20-28: Check uniformity:
• Start with val at (x, y).
• Scan region; if any mismatch, uniform = False.
• Line 31-32: If uniform, return leaf node with val.
• Line 35-38: Split into quadrants:
• Half size (e.g., 4 → 2).
• Recurse on four regions: TL (x, y), TR (x, y+half), BL (x+half, y), BR (x+half, y+half).
• Return non-leaf node with children.
• Line 41: Start with full grid (0, 0, n).
• Time Complexity: O(n² * log n)—each level checks n² cells, log n levels.
• Space Complexity: O(log n)—recursion stack.

This is like slicing a grid into perfect puzzle pieces!

Alternative Solution: Iterative with Matrix Traversal

Why an Alternative Approach?

The iterative with matrix traversal method processes the grid level-by-level, building the Quad Tree bottom-up by checking regions and merging them. It’s O(n² * log n) time and O(n²) space—more explicit but uses extra memory. It’s like assembling the tree floor-by-floor with a grid map!

How It Works

Picture it as building up layers:

• Step 1: Start with leaf nodes (1×1 regions).
• Step 2: Merge four leaves into parents iteratively.
• Step 3: Continue until root.

Step-by-Step Example

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

• Level 1: Leaves:
• (0,0): 0, (0,1): 1, (1,0): 1, (1,1): 0.
• Level 2: Merge:
• Check 2×2: Not uniform.
• Root: Non-leaf with TL=0, TR=1, BL=1, BR=0.
• Result: Root node.

Code for Iterative Approach (Simplified)

Copy codeclass Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':
        if not grid:
            return None

        n = len(grid)
        # Build leaf nodes for 1x1
        nodes = [[None] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                nodes[i][j] = Node(grid[i][j], True, None, None, None, None)

        # Iteratively merge
        size = 1
        while size < n:
            new_nodes = [[None] * (n // 2) for _ in range(n // 2)]
            for i in range(0, n, size * 2):
                for j in range(0, n, size * 2):
                    tl = nodes[i][j]
                    tr = nodes[i][j + size] if j + size < n else None
                    bl = nodes[i + size][j] if i + size < n else None
                    br = nodes[i + size][j + size] if i + size < n and j + size < n else None
                    if (tl.isLeaf and tr and tr.isLeaf and bl and bl.isLeaf and br and br.isLeaf and
                        tl.val == tr.val == bl.val == br.val):
                        new_nodes[i // (size * 2)][j // (size * 2)] = Node(tl.val, True, None, None, None, None)
                    else:
                        new_nodes[i // (size * 2)][j // (size * 2)] = Node(0, False, tl, tr, bl, br)
            nodes = new_nodes
            size *= 2

        return nodes[0][0]

• Time Complexity: O(n² * log n)—each level processes n² cells.
• Space Complexity: O(n²)—nodes matrix.

It’s a layer-by-layer builder!

Comparing the Two Solutions

• Recursive Divide-and-Conquer (Best):
• Pros: O(n² * log n), O(log n), elegant and lean.
• Cons: Recursion depth.
• Iterative Traversal (Alternative):
• Pros: O(n² * log n), O(n²), explicit levels.
• Cons: More space.

Recursive wins for efficiency.

Additional Examples and Edge Cases

• [[1]]: Leaf(1).
• [[0,0],[0,0]]: Leaf(0).
• [[1,1],[0,1]]: Non-leaf with leaves.

Recursive handles all.

Complexity Breakdown

• Recursive: Time O(n² * log n), Space O(log n).
• Iterative: Time O(n² * log n), Space O(n²).

Recursive’s the champ.

Key Takeaways

• Recursive: Divide smart!
• Iterative: Build it up!
• Quad Tree: Splits rule.
• Python Tip: Recursion rocks—see [Python Basics](/python/basics).

Final Thoughts: Construct That Tree

LeetCode 427: Construct Quad Tree in Python is a grid-dividing adventure. Recursive divide-and-conquer slices it fast, while iterative traversal builds it steady. Want more tree fun? Try LeetCode 208: Implement Trie (Prefix Tree) or LeetCode 558: Logical OR of Two Binary Grids Represented as Quad-Trees. Ready to split? Head to Solve LeetCode 427 on LeetCode and construct that Quad Tree today!