Domain 2MediumCORE

Construct Quad Tree

We are given an $N times N$ binary matrix (grid) where $N$ is a power of 2. We need to construct the root node of a Quad-Tree representing this grid. The tree structure follows specific rules: if all values in a sub-grid region are identical, that region becomes a leaf node; otherwise, it splits into four quadrants (Top-Left, Top-Right, Bottom-Left, Bottom-Right).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#FAANG asked: 0

427. Construct Quad Tree

Model: qwen3.5:9b
Topics:
FAANG asked: 0
Acceptance rate: 62.7%


Problem Breakdown

We are given an N×NN \times N binary matrix (grid) where NN is a power of 2. We need to construct the root node of a Quad-Tree representing this grid. The tree structure follows specific rules: if all values in a sub-grid region are identical, that region becomes a leaf node; otherwise, it splits into four quadrants (Top-Left, Top-Right, Bottom-Left, Bottom-Right).

Inputs: A 2D list of integers (grid) containing only 0s and 1s. Outputs: The root object of the Quad-Tree structure defined by a specific class schema. Note that while problem descriptions often show serialized outputs (lists), standard implementation returns the Node object itself, which is what we will return here to adhere to engineering best practices for tree construction problems unless serialization logic is explicitly requested in function signature. Constraints: NN ranges from 1 up to 26=642^6 = 64. This small constraint allows us to focus on correctness and recursion without worrying about massive memory overhead, though the algorithm remains efficient (O(N2)O(N^2)).

Intuition

The core logic is Divide and Conquer. We treat each sub-grid as a potential node. To decide if it’s a leaf or an internal node:

  1. Check if all values in the current region are identical (e.g., check corners, then verify against top-left). If yes -> Leaf Node (isLeaf = True).
  2. If no -> Internal Node (isLeaf = False), split into four quadrants of half size and recurse on each quadrant.

A brute-force approach might try to build the tree by slicing grids repeatedly (O(N3)O(N^3) or worse due to copying). However, since we only need coordinates (row/col) and dimensions for recursion, passing indices avoids grid copies entirely. The key insight is that at any level of recursion depth dd, all active sub-grids combined cover exactly the original area once more effectively if we consider total work done scanning cells across levels sums to O(N2)O(N^2) because each cell belongs to a specific leaf path or internal node check proportional to its size in the hierarchy.

Approach

We will use a recursive helper function build(r, c, side) where (r, c) is top-left coordinate and side is current sub-grid dimension (N→N/2N \to N/2).

  1. Base Case: If all cells within [grid[r][c] ... grid[r+size-1]][[c...]] are the same (check against a reference value, e.g., top-left), create a Leaf Node with that value and isLeaf=True. Return it immediately to stop recursion for this branch.
  2. Recursive Step: If values differ: Create an Internal Node (isLeaf=False). Recursively call build on the four quadrants (TL, TR, BL, BR) passing updated coordinates and half size (side//2side // 2). Assign these returned nodes to children properties. Return root node.
  3. Optimization: Instead of scanning every cell for uniformity at each step blindly, we can check if corners differ or iterate efficiently. Given N≤64N \le 64, a simple iteration over the sub-grid is acceptable and clearer (O(N2)O(N^2) total time).

Complexity Analysis

  • Time Complexity: O(N2)O(N^2). Although recursion seems to multiply work, at each depth level of the tree (from root down), we process disjoint regions that sum up exactly to the original grid size. We visit every cell in the input matrix a constant number of times across all recursive calls effectively because once a region is determined uniform or split, its cells are accounted for.
  • Space Complexity: O(N2)O(N^2) (Worst Case). In cases like a checkerboard pattern where no large uniform regions exist, we create nodes proportional to the grid size (N×NN \times N leaves in worst case if every cell is distinct leaf? No, max depth log⁡N\log N, but total nodes can be up to 4depth4^{\text{depth}}. Actually for Quad Tree on binary matrix, number of internal nodes + leaves roughly correlates with area. Specifically, space includes the tree structure itself which stores pointers and values proportional to grid size in worst case). Recursion stack is O(log⁡N)O(\log N).

Solution

class Node:
    def __init__(self):
        self.val = False
        self.isLeaf = False
        self.topLeft = None
        self.topRight = None
        self.bottomLeft = None
        self.bottomRight = None

def construct(grid):
    if not grid or len(grid) == 0:
        return Node() # Should handle empty input gracefully, though constraints say n >= 1
    
    def build(r, c, size):
        # Base case check for uniformity within current sub-grid [r:r+size][c:c+size]
        val = grid[r][c]
        
        # Check if all cells in this quadrant match 'val'
        is_uniform = True
        for i in range(r, r + size):
            for j in range(c, c + size):
                if grid[i][j] != val:
                    is_uniform = False
                    break
            
            if not is_uniform:
                break
        
        # If uniform, create leaf node
        if is_uniform:
            root = Node()
            root.val = (val == 1) or True # Store as boolean per class def
            root.isLeaf = True
            return root

        # Not uniform -> Internal node with arbitrary val (use top-left for consistency)
        root = Node()
        root.val = grid[r][c] is not None and bool(grid[r][c]) 
        root.isLeaf = False
        
        half_size = size // 2
        
        # Recurse on four quadrants
        root.topLeft = build(r, c, half_size)
        root.topRight = build(r, c + half_size, half_size)
        root.bottomLeft = build(r + half_size, c, half_size)
        root.bottomRight = build(r + half_size, c + half_size, half_size)
        
        return root

    # Initial call with full grid dimensions (N x N)
    n = len(grid)
    return build(0, 0, n)

Edge Cases Handled

  • Single Cell Grid (1×11 \times 1): The loop for uniformity runs once. is_uniform remains True. Returns a Leaf Node immediately without recursion depth issues.
  • All Identical Values: Root node is created as a Leaf with val=True/False. No children are assigned (all null). Correctly handled by the base case check at top level.
  • Checkerboard Pattern (N=2N=2): Top-left and others differ immediately. Recursion splits until size 1, creating leaves for every cell. Handled correctly as internal nodes propagate down to leaf depth log⁡N\log N.
  • Mixed Values: The loop breaks early on mismatch (is_uniform = False), preventing unnecessary full scans if a difference is found quickly (though worst case remains O(N2)O(N^2)).