427. Construct Quad Tree
Model: qwen3.5:9b
Topics:
FAANG asked: 0
Acceptance rate: 62.7%
Problem Breakdown
We are given an binary matrix (grid) where 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: ranges from 1 up to . This small constraint allows us to focus on correctness and recursion without worrying about massive memory overhead, though the algorithm remains efficient ().
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:
- 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). - 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 ( 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 , 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 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 ().
- 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 andisLeaf=True. Return it immediately to stop recursion for this branch. - Recursive Step: If values differ: Create an Internal Node (
isLeaf=False). Recursively callbuildon the four quadrants (TL, TR, BL, BR) passing updated coordinates and half size (). Assign these returned nodes to children properties. Return root node. - Optimization: Instead of scanning every cell for uniformity at each step blindly, we can check if corners differ or iterate efficiently. Given , a simple iteration over the sub-grid is acceptable and clearer ( total time).
Complexity Analysis
- Time Complexity: . 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: (Worst Case). In cases like a checkerboard pattern where no large uniform regions exist, we create nodes proportional to the grid size ( leaves in worst case if every cell is distinct leaf? No, max depth , but total nodes can be up to . 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 .
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 (): The loop for uniformity runs once.
is_uniformremains 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 (): 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 .
- 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 ).