Construct Quad Tree
Construct Quad Tree is a medium recursion & backtracking problem solved with the divide and conquer pattern.
The best approach, optimal (merge children bottom-up), runs in O(n²) time and O(log n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan each square, then split) up.
Problem
You get 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 the root.
Each tree Node has a boolean val, a boolean isLeaf, and four children topLeft, topRight, bottomLeft, bottomRight. A square region whose cells are all equal becomes a leaf (isLeaf = true, val = that value, no children). A mixed region becomes an internal node (isLeaf = false, any val) whose four children describe its four equal quadrants, built the same way.
The tree is shown in level order: each node as [isLeaf, val] (internal nodes always print as [0,1]), null where a node has no child, and trailing nulls removed.
Examples
Example 1
- Input
grid = [[0,0],[0,1]]- Output
[[0,1],[1,0],[1,0],[1,0],[1,1]]- Why
- The 2 x 2 square mixes values, so the root splits into four 1 x 1 leaves: 0, 0, 0 and 1.
Example 2
- Input
grid = [[1,1,0,0],[1,1,0,0],[1,1,1,1],[1,1,1,1]]- Output
[[0,1],[1,1],[1,0],[1,1],[1,1]]- Why
- The whole square is mixed, but each of its four 2 x 2 quadrants is uniform, so every child is a leaf.
Example 3
- Input
grid = [[1,1],[1,1]]- Output
[[1,1]]- Why
- Every cell is 1, so the tree is a single leaf.
Constraints
n == grid.length == grid[i].lengthn == 2^xwhere0 <= x <= 6grid[i][j]is0or1
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (scan each square, then split) | O(n² log n) | O(log n) |
| Optimal (merge children bottom-up) | O(n²) | O(log n) |
1Brute force (scan each square, then split)
O(n² log n)On each of the log n levels of recursion the scans together touch at most all n² cells.O(log n)The recursion depth is log n (not counting the output tree).Recurse on squares. For the current square, scan every cell; if they all match, return a leaf with that value. Otherwise split the square into four halves and recurse on each.
- Call build(row, col, size) for the whole grid.
- Scan all size x size cells; if every cell equals the top-left one, return a leaf with that value.
- Otherwise let half = size / 2 and build the four quadrants: top-left, top-right, bottom-left, bottom-right.
- Return an internal node (isLeaf = false) holding those four children.
class Solution {
public Node construct(int[][] grid) {
return build(grid, 0, 0, grid.length);
}
private Node build(int[][] grid, int r, int c, int size) {
boolean same = true;
for (int i = r; i < r + size && same; i++) {
for (int j = c; j < c + size; j++) {
if (grid[i][j] != grid[r][c]) {
same = false;
break;
}
}
}
if (same) {
return new Node(grid[r][c] == 1, true);
}
int h = size / 2;
return new Node(true, false,
build(grid, r, c, h),
build(grid, r, c + h, h),
build(grid, r + h, c, h),
build(grid, r + h, c + h, h));
}
}class Solution:
def construct(self, grid: List[List[int]]) -> 'Node':
def build(r: int, c: int, size: int) -> 'Node':
first = grid[r][c]
same = all(grid[i][j] == first
for i in range(r, r + size)
for j in range(c, c + size))
if same:
return Node(first == 1, True, None, None, None, None)
h = size // 2
return Node(True, False,
build(r, c, h),
build(r, c + h, h),
build(r + h, c, h),
build(r + h, c + h, h))
return build(0, 0, len(grid))class Solution {
public:
Node* construct(vector<vector<int>>& grid) {
return build(grid, 0, 0, grid.size());
}
private:
Node* build(vector<vector<int>>& grid, int r, int c, int size) {
bool same = true;
for (int i = r; i < r + size && same; i++) {
for (int j = c; j < c + size; j++) {
if (grid[i][j] != grid[r][c]) {
same = false;
break;
}
}
}
if (same) {
return new Node(grid[r][c] == 1, true);
}
int h = size / 2;
return new Node(true, false,
build(grid, r, c, h),
build(grid, r, c + h, h),
build(grid, r + h, c, h),
build(grid, r + h, c + h, h));
}
};function construct(grid) {
const build = (r, c, size) => {
let same = true;
for (let i = r; i < r + size && same; i++) {
for (let j = c; j < c + size; j++) {
if (grid[i][j] !== grid[r][c]) {
same = false;
break;
}
}
}
if (same) {
return new Node(grid[r][c] === 1, true, null, null, null, null);
}
const h = size / 2;
return new Node(true, false,
build(r, c, h),
build(r, c + h, h),
build(r + h, c, h),
build(r + h, c + h, h));
};
return build(0, 0, grid.length);
}2Optimal (merge children bottom-up)
O(n²)The recursion visits each cell once as a 1 x 1 square, and each internal square does O(1) merge work; there are fewer than n² internal squares.O(log n)The recursion depth is log n (not counting the output tree).Always split first and decide on the way back up. A 1 x 1 square is a leaf. After building the four quadrants, if all four are leaves carrying the same value, the square is uniform and collapses into one leaf; otherwise it is an internal node with those children. Every cell is read exactly once.
- build(row, col, size): if size == 1, return a leaf with grid[row][col].
- Build the four quadrants of size size / 2.
- If all four are leaves and their values are equal, return a new leaf with that value.
- Otherwise return an internal node with the four quadrants as children.
class Solution {
public Node construct(int[][] grid) {
return build(grid, 0, 0, grid.length);
}
private Node build(int[][] grid, int r, int c, int size) {
if (size == 1) {
return new Node(grid[r][c] == 1, true);
}
int h = size / 2;
Node tl = build(grid, r, c, h);
Node tr = build(grid, r, c + h, h);
Node bl = build(grid, r + h, c, h);
Node br = build(grid, r + h, c + h, h);
if (tl.isLeaf && tr.isLeaf && bl.isLeaf && br.isLeaf
&& tl.val == tr.val && tr.val == bl.val && bl.val == br.val) {
return new Node(tl.val, true);
}
return new Node(true, false, tl, tr, bl, br);
}
}class Solution:
def construct(self, grid: List[List[int]]) -> 'Node':
def build(r: int, c: int, size: int) -> 'Node':
if size == 1:
return Node(grid[r][c] == 1, True, None, None, None, None)
h = size // 2
tl = build(r, c, h)
tr = build(r, c + h, h)
bl = build(r + h, c, h)
br = build(r + h, c + h, h)
kids = (tl, tr, bl, br)
if all(k.isLeaf for k in kids) and tl.val == tr.val == bl.val == br.val:
return Node(tl.val, True, None, None, None, None)
return Node(True, False, tl, tr, bl, br)
return build(0, 0, len(grid))class Solution {
public:
Node* construct(vector<vector<int>>& grid) {
return build(grid, 0, 0, grid.size());
}
private:
Node* build(vector<vector<int>>& grid, int r, int c, int size) {
if (size == 1) {
return new Node(grid[r][c] == 1, true);
}
int h = size / 2;
Node* tl = build(grid, r, c, h);
Node* tr = build(grid, r, c + h, h);
Node* bl = build(grid, r + h, c, h);
Node* br = build(grid, r + h, c + h, h);
if (tl->isLeaf && tr->isLeaf && bl->isLeaf && br->isLeaf
&& tl->val == tr->val && tr->val == bl->val && bl->val == br->val) {
bool v = tl->val;
delete tl; delete tr; delete bl; delete br;
return new Node(v, true);
}
return new Node(true, false, tl, tr, bl, br);
}
};function construct(grid) {
const build = (r, c, size) => {
if (size === 1) {
return new Node(grid[r][c] === 1, true, null, null, null, null);
}
const h = size / 2;
const tl = build(r, c, h);
const tr = build(r, c + h, h);
const bl = build(r + h, c, h);
const br = build(r + h, c + h, h);
if (tl.isLeaf && tr.isLeaf && bl.isLeaf && br.isLeaf
&& tl.val === tr.val && tr.val === bl.val && bl.val === br.val) {
return new Node(tl.val, true, null, null, null, null);
}
return new Node(true, false, tl, tr, bl, br);
};
return build(0, 0, grid.length);
}Edge cases to test
- A 1 x 1 grid: the root is a leaf
- A grid where every cell is the same: one leaf, no splitting at all
- A checkerboard: every square of size above 1 is mixed, so the tree goes all the way down
- Four uniform quadrants with the same value must merge into a single leaf, not four
Hints
Hint 1
A square becomes a leaf exactly when all its cells hold the same value. Otherwise it splits into four equal quadrants.
Hint 2
Checking each square by scanning it repeats work. Build the four children first: if all four are leaves with the same value, the parent can be that leaf instead.
FAQ
What is the best time complexity for Construct Quad Tree?
Optimal (merge children bottom-up) runs in O(n²) time and O(log n) extra space. The recursion visits each cell once as a 1 x 1 square, and each internal square does O(1) merge work; there are fewer than n² internal squares.
Which pattern does Construct Quad Tree use?
It is a recursion & backtracking problem that uses the divide and conquer pattern. Other problems with the same pattern: Special Binary String.
Is there a brute force solution for Construct Quad Tree?
Yes. Brute force (scan each square, then split) takes O(n² log n) time and O(log n) space. Recurse on squares.
Which edge cases should I test for Construct Quad Tree?
A 1 x 1 grid: the root is a leaf; A grid where every cell is the same: one leaf, no splitting at all; A checkerboard: every square of size above 1 is mixed, so the tree goes all the way down; Four uniform quadrants with the same value must merge into a single leaf, not four.