Construct Quad Tree

Medium Top 250

Associated Patterns

Interviewed At (Company Tags)

GoogleUber

Problem Description

Given a n * n matrix grid of 0's and 1's only. We want to represent grid with a Quad-Tree. Return the root of the Quad-Tree representing the grid.

A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:

val: True if the node represents a grid of 1’s or False if the node represents a grid of 0’s.
isLeaf: True if the node is leaf node on the tree or False if the node has the four children.

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

We can construct a Quad-Tree from a two-dimensional area using the following steps:

If the current grid has the same value (i.e. all 1's or all 0's), set isLeaf True and set val to the value of the grid and set the four children to Null and stop.
If the current grid has different values, set isLeaf False and set val to any value and divide the current grid into four sub-grids.
Recurse for each of the children with the proper sub-grids.

Examples

Example 1:

Input: grid = [[0,1],[1,0]] Output: [[0,1],[1,0],[1,1],[1,1],[1,0]] Explanation: The grid is divided into 4 sub-grids. Since they have different values, the root node is not a leaf node and has 4 children.

Constraints

n == grid.length == grid[i].length
n == 2ˣ where 0 <= x <= 6

Divide and Conquer Sub-matrix Partitioning

To construct a Quad-Tree:

Write a recursive helper function construct(rowStart, colStart, size) representing the subgrid.
Check if all cells in the subgrid have the same value. If they do:
- Create a leaf node with val = grid[rowStart][colStart] and isLeaf = true.
If they differ, create an internal node with isLeaf = false and recursively partition the subgrid into four quadrants of size size / 2:
- topLeft = construct(rowStart, colStart, size/2)
- topRight = construct(rowStart, colStart + size/2, size/2)
- bottomLeft = construct(rowStart + size/2, colStart, size/2)
- bottomRight = construct(rowStart + size/2, colStart + size/2, size/2) Return the root node.

Solution 1: Divide and Conquer Quad Partitioning

Check if subgrid cells match, then split into four smaller subgrids recursively.

/*
// Definition for a QuadTree node.
class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;

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

class Solution {
    public Node construct(int[][] grid) {
        return helper(grid, 0, 0, grid.length);
    }

    private Node helper(int[][] grid, int r, int c, int size) {
        if (allSame(grid, r, c, size)) {
            return new Node(grid[r][c] == 1, true);
        }

        Node root = new Node(true, false);
        int half = size / 2;
        root.topLeft = helper(grid, r, c, half);
        root.topRight = helper(grid, r, c + half, half);
        root.bottomLeft = helper(grid, r + half, c, half);
        root.bottomRight = helper(grid, r + half, c + half, half);

        return root;
    }

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

# """
# Definition for a QuadTree node.
# class Node:
#     def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
#         self.val = val
#         self.isLeaf = isLeaf
#         self.topLeft = topLeft
#         self.topRight = topRight
#         self.bottomLeft = bottomLeft
#         self.bottomRight = bottomRight
# """

class Solution:
    def construct(self, grid: list[list[int]]) -> 'Node':
        
        def helper(r: int, c: int, size: int) -> 'Node':
            if all_same(r, c, size):
                return Node(grid[r][c] == 1, True, None, None, None, None)
                
            half = size // 2
            topLeft = helper(r, c, half)
            topRight = helper(r, c + half, half)
            bottomLeft = helper(r + half, c, half)
            bottomRight = helper(r + half, c + half, half)
            
            return Node(True, False, topLeft, topRight, bottomLeft, bottomRight)
            
        def all_same(r: int, c: int, size: int) -> bool:
            val = grid[r][c]
            for i in range(r, r + size):
                for j in range(c, c + size):
                    if grid[i][j] != val:
                        return False
            return True

        return helper(0, 0, len(grid))

/*
// Definition for a QuadTree node.
class Node {
public:
    bool val;
    bool isLeaf;
    Node* topLeft;
    Node* topRight;
    Node* bottomLeft;
    Node* bottomRight;
    
    Node() {
        val = false;
        isLeaf = false;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
};
*/

class Solution {
private:
    bool allSame(const std::vector<std::vector<int>>& grid, int r, int c, int size) {
        int val = grid[r][c];
        for (int i = r; i < r + size; i++) {
            for (int j = c; j < c + size; j++) {
                if (grid[i][j] != val) return false;
            }
        }
        return true;
    }

    Node* helper(const std::vector<std::vector<int>>& grid, int r, int c, int size) {
        if (allSame(grid, r, c, size)) {
            return new Node(grid[r][c] == 1, true);
        }

        Node* root = new Node(true, false);
        int half = size / 2;
        root->topLeft = helper(grid, r, c, half);
        root->topRight = helper(grid, r, c + half, half);
        root->bottomLeft = helper(grid, r + half, c, half);
        root->bottomRight = helper(grid, r + half, c + half, half);

        return root;
    }

public:
    Node* construct(std::vector<std::vector<int>>& grid) {
        return helper(grid, 0, 0, grid.size());
    }
};

Complexity Analysis

Time Complexity: O(n² log n) since checking if all cells are the same takes O(size²) at each level, and there are log n levels. (Can be optimized to O(n²) using 2D prefix sums to verify cell uniformity in O(1)).
Space Complexity: O(log n) auxiliary space due to the recursion call stack.