Construct Quad Tree
Medium · Arrays & Hashing · Array · Divide and Conquer · Tree · Matrix
Problem
You are given an n x n matrix grid of 0s and 1s, where n is a power of two. Represent it as a quad tree and return its root.
Every node has isLeaf and val, plus four children topLeft, topRight, bottomLeft and bottomRight. The node for a square region is built like this:
- if every cell in the region holds the same value, the node is a leaf: isLeaf = True, val is that value (True for 1, False for 0), and it has no children;
- otherwise isLeaf = False (its val may be anything), and the region is cut into four equal quadrants whose nodes become its four children, built the same way.
Create nodes with Node(val, isLeaf, topLeft, topRight, bottomLeft, bottomRight). The grader writes your tree in level order, each node as [isLeaf, val] (1/0), None for a missing child, children in the order topLeft, topRight, bottomLeft, bottomRight, trailing Nones dropped. Internal nodes are written [0, 1] whatever their val.
Examples
Input: grid = [[1,1],[1,1]] Output: [[1,1]]
The whole grid is 1s, so the root is a single leaf.
Input: grid = [[1,0],[0,1]] Output: [[0,1],[1,1],[1,0],[1,0],[1,1]]
The cells differ, so the root splits into four one-cell leaves: 1, 0, 0, 1.
Input: grid = [[0,0,1,0],[0,0,0,1],[1,1,1,1],[1,1,1,1]] Output: [[0,1],[1,0],[0,1],[1,1],[1,1],None,None,None,None,[1,1],[1,0],[1,0],[1,1]]
Only the top-right quadrant is mixed, so it alone splits again. The four Nones are the missing children of the top-left leaf.
Constraints
- n == len(grid) == len(grid[i])
- n == 2^x with 0 <= x <= 6
- grid[i][j] is 0 or 1
Approaches
- Scan each square, split if mixed — time O(n² log n), space O(log n) recursion
Follow-up
With a 2-D prefix sum you can test any square for uniformity in O(1) (its sum is 0 or its area), so the top-down version also becomes O(n²) without building tiny leaves first. Quad trees also support set operations: the OR of two quad trees can be computed node by node without expanding either back into a grid.
Related problems
Start free on Cariara · Coding problems · System design studio
