427. Construct Quad Tree

NeetCode: Construct Quad Tree · LeetCode: 427. Construct Quad Tree · Difficulty: Medium

Given an n x n grid of 0s and 1s (with n a power of two), build its quad tree. Each node has a val (true for 1), an isLeaf flag, and four children: top-left, top-right, bottom-left, bottom-right. If a region holds a single value it becomes a leaf with that value; otherwise it becomes an internal node whose four children are the quad trees of the four equal quadrants.

Example

Input:  grid = [[0,1],[1,0]]
Output: an internal node with four leaves: 0, 1, 1, 0  (top-left, top-right, bottom-left, bottom-right)

Input:  grid = [[1,1],[1,1]]
Output: a single leaf with value 1

The programs below print the tree in preorder. A leaf prints as L0 or L1, and an internal node prints as ( followed by its four children and ). So the first example prints (L0L1L1L0). Missing children are null; the Node class has LeetCode's field names and constructors.

Brute force: recurse with an isUniform scan

Recursion on a square region (r, c, size): an isUniform helper scans every cell of the region. If they are all equal, return a leaf. Otherwise split into four quadrants of half the size and recurse.

The scan stops at the first differing cell, but in the worst case (a region that is uniform except for its last cell, at every level) it reads the whole region. On each level of recursion the regions partition the grid, so a level costs O(n^2) in total, and there are log n levels.

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;

    public Node(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
    }

    public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
}

class Solution {
    private boolean isUniform(int[][] grid, int r, int c, int size) {
        int first = grid[r][c];
        for (int i = r; i < r + size; i++) {
            for (int j = c; j < c + size; j++) {
                if (grid[i][j] != first) {
                    return false;
                }
            }
        }
        return true;
    }

    private Node build(int[][] grid, int r, int c, int size) {
        if (isUniform(grid, r, c, size)) {
            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));
    }

    public Node construct(int[][] grid) {
        if (grid.length == 0) {
            return null;
        }
        return build(grid, 0, 0, grid.length);
    }
}

public class Main {
    static String serialize(Node node) {
        if (node == null) {
            return "";
        }
        if (node.isLeaf) {
            return "L" + (node.val ? 1 : 0);
        }
        return "(" + serialize(node.topLeft) + serialize(node.topRight)
            + serialize(node.bottomLeft) + serialize(node.bottomRight) + ")";
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(serialize(s.construct(new int[][] {{0, 1}, {1, 0}})));
        System.out.println(serialize(s.construct(new int[][] {{1, 1}, {1, 1}})));
        int[][] grid = {
            {1, 1, 0, 0},
            {1, 1, 0, 0},
            {0, 0, 1, 1},
            {0, 0, 1, 0},
        };
        System.out.println(serialize(s.construct(grid)));
        System.out.println("[" + serialize(s.construct(new int[0][0])) + "]");
    }
}

(L0L1L1L0)
L1
(L1L0L0(L1L1L1L0))
[]

Time: O(n^2 log n), where the grid is n x n. Space: O(n^2) in the worst case for the tree, plus O(log n) recursion.

Steps: (1) if the region is uniform, return a leaf with that value; (2) otherwise recurse into the four quadrants of half the size and return an internal node. A 2D prefix-sum table makes the uniformity check O(1) (a region is uniform when its sum is 0 or size * size) and brings the whole build to O(n^2). The scan version is fast enough for small grids.

How to explain it in an interview

• Say first: recurse on a region; if all its cells are equal make a leaf, else split into four quadrants and recurse. The uniform scan costs O(n^2) per level over log n levels.
• Key insight: the problem statement is already the recursion, so the code is a direct translation: leaf if uniform, otherwise four children.
• Code it in steps: (1) isUniform(r, c, size); (2) build(r, c, size) returning a leaf when uniform; (3) otherwise h = size / 2 and four recursive calls in the order top-left, top-right, bottom-left, bottom-right.
• Complexity to state: time O(n^2 log n) worst case, space O(n^2) for the tree plus O(log n) recursion.
• Likely follow-ups / pitfalls: speeding up the uniformity check (2D prefix sums, O(n^2) total); the child order (top-left, top-right, bottom-left, bottom-right); a leaf's val is the shared cell value, while an internal node's val is arbitrary.

Interview points

• A region of equal cells becomes a leaf; any other region splits into four equal quadrants.
• The scan-based version costs O(n^2 log n); prefix sums give O(n^2).
• The child order is top-left, top-right, bottom-left, bottom-right.

Summary

• Each recursion level partitions the grid, so one level costs O(n^2) in the worst case, and there are log n levels.
• A leaf's val is the shared cell value; an internal node's val is arbitrary.
• The tree has O(n^2) nodes in the worst case.