#427 Construct Quad Tree
frequently reported atUber
the problem
In plain words
You get an n × n grid of 0s and 1s, where n is a power of two. Build its quad tree and return the root. A square whose cells all hold one value is a leaf: isLeaf = true, val = that value (1 → true), four null children. A mixed square is an internal node: isLeaf = false, val can be anything, and its four children are its top-left, top-right, bottom-left and bottom-right quarters, built the same way. The node class has the fields val, isLeaf, topLeft, topRight, bottomLeft, bottomRight.
in grid = [[0,1],[1,0]]
out [[0,1],[1,0],[1,1],[1,1],[1,0]]
The 2×2 square is mixed, so the root splits; each 1×1 quarter is a leaf. The output lists nodes level by level as [isLeaf, val].
in 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]]
out [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
Top-left, bottom-left and bottom-right 4×4 quarters each hold one value → leaves. The top-right quarter is mixed, so it splits into four 2×2 leaves. `null`s mark the missing children of the first leaf.
- n == grid.length == grid[i].length
- n = 2ˣ with 0 ≤ x ≤ 6 (so n ≤ 64)
- grid[i][j] is 0 or 1
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternDivide and conquerRecursion on a smaller input
where this runsMap tiles use the same split: Bing Maps names each tile with a quadkey, one digit per level, each digit picking one of four sub-tiles.
A square is a leaf exactly when all its cells match. Otherwise its node is built from four smaller copies of the same problem — so trust four recursive calls, then decide: four leaves with the same value merge into one leaf.
solutions
From brute force to optimal
Top-down: check every cell of the current square; one value → leaf, otherwise recurse on the four quarters.
- Describe a square by (row, col, size) — never copy sub-grids.
- Scan its size² cells against the first cell.
- All equal → return a leaf with that value.
- Mixed → return an internal node whose children are the four quarters of size / 2.
Each level of the tree scans at most all n² cells once in total, and there are log₂ n + 1 levels (7 for n = 64).
Recursion depth is log₂ n + 1; the tree itself is the output.
class Solution { public Node construct(int[][] grid) { return build(grid, 0, 0, grid.length); } /** The square with top-left corner (row, col) and side `size`. */ private Node build(int[][] grid, int row, int col, int size) { if (allSame(grid, row, col, size)) { // scan every cell of this square return new Node(grid[row][col] == 1, true); // one value → a leaf } int half = size / 2; // mixed → split into four smaller squares return new Node(true, false, build(grid, row, col, half), // top-left build(grid, row, col + half, half), // top-right build(grid, row + half, col, half), // bottom-left build(grid, row + half, col + half, half)); // bottom-right } private boolean allSame(int[][] grid, int row, int col, int size) { for (int r = row; r < row + size; r++) for (int c = col; c < col + size; c++) if (grid[r][c] != grid[row][col]) return false; return true; }}Watch the grid split
Bottom-up: a 1×1 square is always a leaf. Build the four quarters; if all four are leaves with the same value, merge them into one leaf.
- Base case: size == 1 → leaf with that cell's value.
- Recurse on the four quarters of size / 2.
- All four are leaves with equal val → return one leaf with that val.
- Otherwise return an internal node holding the four children.
Every cell is read once at the 1×1 level; each bigger square does O(1) merge work, and there are fewer than n² / 3 of them.
Recursion depth is log₂ n + 1. (Leaves that get merged become garbage for the GC to reclaim.)
class Solution { public Node construct(int[][] grid) { return build(grid, 0, 0, grid.length); } private Node build(int[][] grid, int row, int col, int size) { if (size == 1) return new Node(grid[row][col] == 1, true); // one cell is always a leaf int half = size / 2; Node topLeft = build(grid, row, col, half); // trust the four smaller calls... Node topRight = build(grid, row, col + half, half); Node bottomLeft = build(grid, row + half, col, half); Node bottomRight = build(grid, row + half, col + half, half); boolean allLeaves = topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf; boolean sameValue = topLeft.val == topRight.val && topLeft.val == bottomLeft.val && topLeft.val == bottomRight.val; if (allLeaves && sameValue) return new Node(topLeft.val, true); // ...then merge 4 equal leaves return new Node(true, false, topLeft, topRight, bottomLeft, bottomRight); }}in the room
How to say it in the interview
talk track
- Restate the rule: one value → leaf; mixed → four children in the order topLeft, topRight, bottomLeft, bottomRight.
- Say you'll pass (row, col, size) instead of copying sub-grids — it keeps every call O(1) apart from its real work.
- Give the top-down scan first (O(n² log n)), then improve: build the children first and merge, so each cell is read once → O(n²).
traps
- Copying sub-grids into new arrays on every call — O(n²) extra copying per level. Pass (row, col, size).
- Mixing up the child order: it must be topLeft, topRight, bottomLeft, bottomRight.
- Merging four children that have equal
valbut are not all leaves — an internal node'svalmeans nothing.
what they ask next
Follow-ups
Can the top-down version check a square in O(1)?
Yes: precompute a 2D prefix sum of the grid. A size × size square is all 0s if its sum is 0 and all 1s if its sum is size². The whole build becomes O(n²).
Logical OR of Two Binary Grids Represented as Quad-Trees (LC 558)?
Recurse on both trees together. A leaf of 1 on either side decides the answer (all 1); a leaf of 0 means "take the other tree". Otherwise OR the four child pairs and merge if all four results are leaves with the same value.
before you submit
Edge cases to test
- n = 1: the root itself is a leaf.
- A grid of one value: the whole tree is a single leaf, whatever n is.
- A checkerboard never merges: for n = 64 that's 4,096 leaves and 1,365 internal nodes.
practise next
Similar problems
- #108
- #912Sort an ArrayMediumin Sorting