Construct Quad Tree
Asked at Uber
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).
Asked At
| Company | Difficulty | |
|---|---|---|
| Uber | Medium | View all Uber 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).
Visual walkthrough for 2x2 grid [[1,1],[1,0]]: not uniform (1 and 0 differ). Split into four 1x1 leaves: TL=1, TR=1, BL=1, BR=0. Internal node isLeaf=false, val=1 (arbitrary for internal).
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.
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
class 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Construct Quad Tree?
Construct Quad Tree is asked at Uber. 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.