427. Construct Quad Tree
Asked at Uber, Snowflake
Difficulty
Medium
Time
O(n^2)
Space
O(n^2)
Pattern
Array
Companies
2
Problem
You are given an n x n grid filled only with 0s and 1s. Build a Quad-Tree that represents this grid and return its root node.
A Quad-Tree node has a val (true means the region is all 1s, false means all 0s) and an isLeaf flag. If a region is uniform — every cell has the same value — the node is a leaf: isLeaf = true, val is that shared value, and all four children are null. If the region is mixed, the node is internal: isLeaf = false, val can be anything, and it has four children for the four quadrants: topLeft, topRight, bottomLeft, bottomRight. You split a region of size s into four sub-regions of size s/2 and recurse on each.
A region of size 1 is always a leaf. The grid size n is a power of two, so it always splits evenly.
Splitting a mixed grid into quadrants
Constraints
- ●
n == grid.length == grid[i].length - ●
n == 2^x where 0 <= x <= 6 - ●
grid[i][j] is 0 or 1
Examples
grid = [[0,1],[1,0]][[0,1],[1,0],[1,1],[1,1],[1,0]]grid = [[1,1],[1,1]][[1,1]]grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]][[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Uber | Medium | View all Uber questions → |
| Snowflake | Medium | View all Snowflake questions → |
How to Think About It
Recursive divide and conquer: check if all values in the current grid region are the same. If yes, create a leaf node. If no, split into four quadrants and recurse on each.
To check if all values are the same: compare the first cell (top-left) with every other cell in the region. If any differ, the region is not uniform. This is O(size^2) per call but total work is O(n^2) because each cell is visited once across all recursion levels.
Quad Tree node structure: val (1 or 0), isLeaf (boolean), topLeft, topRight, bottomLeft, bottomRight. Leaf nodes have all four children as NULL.
Splitting: for a region from (r, c) with size s, the four quadrants are: TL=(r, c, s/2), TR=(r, c+s/2, s/2), BL=(r+s/2, c, s/2), BR=(r+s/2, c+s/2, s/2).
Base case: if size is 1, always a leaf with that single value. If all cells in the region are 0 or all are 1, create a leaf. Otherwise recurse.
Optimal Approach
Step 1: Define a helper function build(r, c, size) that processes the grid region starting at (r, c) with the given size.
Step 2: If size is 1, return a leaf node with grid[r][c].
Step 3: Check if all cells in the region are the same as grid[r][c]. If yes, return a leaf node.
Step 4: Otherwise, split into four quadrants and recurse:
- topLeft = build(r, c, size/2)
- topRight = build(r, c + size/2, size/2)
- bottomLeft = build(r + size/2, c, size/2)
- bottomRight = build(r + size/2, c + size/2, size/2)
Step 5: Return an internal node with isLeaf=false and the four children.
Walkthrough for [[1,1],[1,1]]: all cells are 1 -> leaf node (val=1, isLeaf=true).
Walkthrough for [[0,1],[1,1]]: not uniform -> split into 4 1x1 leaves: TL=0, TR=1, BL=1, BR=1.
Time: O(n^2) - each cell is checked once across all recursion levels. Space: O(n^2) for the quad tree nodes.
Recursive divide and conquer
What Trips People Up in Real Interviews
Forgetting that internal nodes still need a val. Set val to 1 if any child is 1, or just 1 by convention (it is ignored for non-leaf nodes).
Wrong quadrant order. The problem specifies: top-left, top-right, bottom-left, bottom-right. Do not mix up row/column offsets.
Not handling the base case of size=1. A 1x1 region is always a leaf regardless of its value.
Checking uniformity incorrectly. You must check ALL cells, not just corners. A region like [[0,1],[0,0]] is not uniform even though three corners are 0.
Returning NULL for uniform regions. A uniform region should return a leaf node (isLeaf=true), not NULL. NULL means no node exists.
Solution Code
O(n^2) timeclass Node:
def __init__(self, val, isLeaf, topLeft=None, topRight=None, bottomLeft=None, bottomRight=None):
self.val = val
self.isLeaf = isLeaf
self.topLeft = topLeft
self.topRight = topRight
self.bottomLeft = bottomLeft
self.bottomRight = bottomRight
class Solution:
def construct(self, grid):
n = len(grid)
def build(r, c, size):
if size == 1:
return Node(grid[r][c] == 1, True)
val = grid[r][c]
same = True
for i in range(r, r + size):
for j in range(c, c + size):
if grid[i][j] != val:
same = False
break
if not same:
break
if same:
return Node(val == 1, True)
s = size // 2
return Node(True, False,
build(r, c, s),
build(r, c + s, s),
build(r + s, c, s),
build(r + s, c + s, s))
return build(0, 0, n)Frequently Asked Questions
What is the Construct Quad Tree problem?
Given an n x n grid of 0s and 1s, construct a Quad Tree. A Quad Tree node is either a leaf (all four values equal) or an internal node with four children representing the four quadrants (top-left, top-right, bottom-left, bottom-right).
How do you solve Construct Quad Tree?
The optimal approach runs in O(n^2) time and O(n^2) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Construct Quad Tree?
Construct Quad Tree is asked at Uber, Snowflake. It is a medium difficulty problem.
What are common mistakes on Construct Quad Tree?
- Forgetting that internal nodes still need a val. Set val to 1 if any child is 1, or just 1 by convention (it is ignored for non-leaf nodes).
- Wrong quadrant order. The problem specifies: top-left, top-right, bottom-left, bottom-right. Do not mix up row/column offsets.
- Not handling the base case of size=1. A 1x1 region is always a leaf regardless of its value.
- Checking uniformity incorrectly. You must check ALL cells, not just corners. A region like [[0,1],[0,0]] is not uniform even though three corners are 0.
- Returning NULL for uniform regions. A uniform region should return a leaf node (isLeaf=true), not NULL. NULL means no node exists.