Construct Quad Tree

Medium Recursion & Backtracking Divide and Conquer Original on LeetCode

Reported atUberPalantir

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].length
  • n == 2^x where 0 <= x <= 6
  • grid[i][j] is 0 or 1

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.

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(n² log n)On each of the log n levels of recursion the scans together touch at most all n² cells.
SpaceO(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.

  1. Call build(row, col, size) for the whole grid.
  2. Scan all size x size cells; if every cell equals the top-left one, return a leaf with that value.
  3. Otherwise let half = size / 2 and build the four quadrants: top-left, top-right, bottom-left, bottom-right.
  4. 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));
    }
}

2Optimal (merge children bottom-up)

TimeO(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.
SpaceO(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.

  1. build(row, col, size): if size == 1, return a leaf with grid[row][col].
  2. Build the four quadrants of size size / 2.
  3. If all four are leaves and their values are equal, return a new leaf with that value.
  4. 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);
    }
}

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.