Construct Quad Tree

Problem Statement

In this problem, you are provided with a square matrix grid, composed solely of 0's and 1's. Your task is to create a Quad-Tree representation of this matrix. The Quad-Tree is a specialized tree data structure where each internal node has exactly four children. It efficiently represents data that is hierarchically divisible into quarters, which perfectly suits the needs of matrix representation where data can be markedly uniform or varied in different sectors.

The challenge lies in constructing this Quad-Tree by dividing the matrix into four quadrants until all cells in a quadrant hold the same value (either all 0's or all 1's). Each node in the Quad-Tree corresponds to a specific sub-grid and is defined with a boolean value and a boolean flag indicating whether it is a leaf node:

• val: captures the predominant boolean value of the sub-grid. For leaf nodes, it represents the value of the area (all 0's or 1's). For non-leaf nodes, it might be arbitrarily set, as the specific mix of children's values describe the grid accurately.
• isLeaf: signifies if the node is a leaf (i.e., the corresponding sub-grid is uniform).

The entire tree needs to be constructed following these principles iteratively or recursively until every part of the grid is represented succinctly in the Quad-Tree structure.

Examples

Example 1

Input:

grid = [[0,1],[1,0]]

Output:

[[0,1],[1,0],[1,1],[1,1],[1,0]]

Explanation:

The explanation of this example is shown below:
Notice that 0 represents False and 1 represents True in the photo representing the Quad-Tree.

Example 2

Input:

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]]

Output:

[[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]

Explanation:

All values in the grid are not the same. We divide the grid into four sub-grids.
The topLeft, bottomLeft and bottomRight each has the same value.
The topRight have different values so we divide it into 4 sub-grids where each has the same value.
Explanation is shown in the photo below:

Constraints

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

Approach and Intuition

Given the constraints and examples, the approach to solve this problem breaks down into several clear steps:

1. Start by examining the entire grid to determine if it's a leaf node:
   • If the grid contains the same value (1's or 0's), create a leaf node indicating this uniformity.
   • If the grid contains both values, proceed to divide the grid into four quadrants or sub-grids.
2. Recursively apply the Quad-Tree construction to each of the four sub-grids:
   • Top-left
   • Top-right
   • Bottom-left
   • Bottom-right
3. During each recursive step, determine the nature of the sub-grid (uniform or mixed):
   • If uniform, mark the recursive call’s return as a leaf node.
   • If mixed, further sub-divide the grid.
4. Each call should return a node which gets assigned to the parent node’s respective children (top-left, top-right, bottom-left, bottom-right).
5. Base case for the recursion would be when the size of the grid becomes 1x1, directly returning a node with the single element as its value and isLeaf set to True.

This method ensures a methodical breakdown of the grid, leveraging the inherent divide-and-conquer paradigm which is suited for hierarchical representations like the Quad-Tree.

Solutions

class Solution {
public:
    Node* constructSubtree(vector<vector<int>>& matrix, int x, int y, int len) {
        if (len == 1) {
            return new Node(matrix[x][y], true);
        }
    
        Node* topLeftNode = constructSubtree(matrix, x, y, len / 2);
        Node* topRightNode = constructSubtree(matrix, x, y + len / 2, len / 2);
        Node* bottomLeftNode = constructSubtree(matrix, x + len / 2, y, len / 2);
        Node* bottomRightNode = constructSubtree(matrix, x + len / 2, y + len / 2, len / 2);
    
        if (topLeftNode -> isLeaf && topRightNode -> isLeaf && 
            bottomLeftNode -> isLeaf && bottomRightNode -> isLeaf &&
            topLeftNode -> val == topRightNode -> val && 
            topRightNode -> val == bottomLeftNode -> val && 
            bottomLeftNode -> val == bottomRightNode -> val) {
            return new Node(topLeftNode -> val, true);
        }
    
        return new Node(false, false, topLeftNode, topRightNode, bottomLeftNode, bottomRightNode);
    }
    
    Node* build(vector<vector<int>>& matrix) {
        return constructSubtree(matrix, 0, 0, matrix.size());
    }
};