# Construct Quad Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/construct-quad-tree)
Canonical: https://scaleengineer.com/dsa/problems/construct-quad-tree
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer)
**Data structures:** Array, Matrix, Tree
**Companies:** [Palantir Technologies](https://scaleengineer.com/companies/palantir-technologies)
---
## Problem
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_ `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. Notice that you can assign the `val` to True or False when `isLeaf` is False, and both are accepted in the answer.
* `isLeaf`: True if the node is a leaf node on the tree or False if the node has 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:

1. 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.
2. If the current grid has different values, set `isLeaf` to False and set `val` to any value and divide the current grid into four sub-grids as shown in the photo.
3. Recurse for each of the children with the proper sub-grid.
![](https://assets.glich.co/dsa/construct-quad-tree/image0.png) 

If you want to know more about the Quad-Tree, you can refer to the [wiki](https://en.wikipedia.org/wiki/Quadtree).

**Quad-Tree format:**

You don't need to read this section for solving the problem. This is only if you want to understand the output format here. The output represents the serialized format of a Quad-Tree using level order traversal, where `null` signifies a path terminator where no node exists below.

It is very similar to the serialization of the binary tree. The only difference is that the node is represented as a list `[isLeaf, val]`.

If the value of `isLeaf` or `val` is True we represent it as **1** in the list `[isLeaf, val]` and if the value of `isLeaf` or `val` is False we represent it as **0**.

**Example 1:**

![](https://assets.glich.co/dsa/construct-quad-tree/image1.png) 

**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.
![](https://assets.glich.co/dsa/construct-quad-tree/image2.png)

**Example 2:**

![](https://assets.glich.co/dsa/construct-quad-tree/image3.png)

**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:
![](https://assets.glich.co/dsa/construct-quad-tree/image4.png)

**Constraints:**

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

# Approaches
## Naive Recursive Approach
This approach directly implements the recursive definition of the Quad Tree construction. A helper function is defined that takes the coordinates and size of the current sub-grid. This function first checks if all values in the sub-grid are the same. If they are, it creates a leaf node. If not, it creates an internal node, divides the grid into four equal quadrants, and makes a recursive call for each quadrant to build the sub-trees.
**Time:** O(N^2 * log N). For each node in the Quad Tree, we iterate over its corresponding sub-grid. The recurrence relation is `T(N) = 4 * T(N/2) + O(N^2)`. At each level of recursion, the total work for the homogeneity check across all nodes at that level is `O(N^2)`. Since the depth of the tree is `log N`, the total time complexity is `O(N^2 * log N)`. · **Space:** O(N^2). The space is dominated by the storage for the Quad Tree itself, which can have `O(N^2)` nodes in the worst-case scenario (e.g., a checkerboard pattern). The recursion stack depth contributes `O(log N)`.
**Pros:** Simple to understand and implement as it directly follows the problem definition.; Does not require any extra data structures for pre-computation.
**Cons:** Inefficient due to redundant computations. The homogeneity check for a sub-grid re-scans cells that were already scanned by its parent's check.
### Explanation
The core of this method is a recursive function, let's call it `build(row, col, size)`. This function is responsible for constructing the Quad Tree for the `size x size` sub-grid starting at `(row, col)`.

The process within `build(row, col, size)` is as follows:
1.  **Homogeneity Check:** First, we determine if the sub-grid is homogeneous (contains all 0s or all 1s). We can do this by taking the value of the top-left cell, `grid[row][col]`, and then iterating through all the cells in the `size x size` sub-grid. If we find any cell with a different value, the grid is not homogeneous.
2.  **Leaf Node Creation:** If the check passes (the grid is homogeneous), we create a new `Node`. We set `isLeaf` to `true`, `val` to the common value (true for 1, false for 0), and all four children pointers to `null`. This node is then returned.
3.  **Internal Node Creation:** If the check fails (the grid has mixed values), we create an internal node. We set `isLeaf` to `false` and `val` to an arbitrary value (e.g., `true`). Then, we divide the current `size x size` grid into four `(size/2) x (size/2)` sub-grids and make recursive calls to `build` for each of these four sub-grids, assigning the returned nodes to the `topLeft`, `topRight`, `bottomLeft`, and `bottomRight` children of the current internal node. This node is then returned.

The initial call to start the process would be `build(0, 0, n)`, where `n` is the dimension of the input grid.

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

    private Node build(int[][] grid, int row, int col, int size) {
        // Check if the sub-grid is homogeneous
        boolean isHomogeneous = true;
        int firstVal = grid[row][col];
        for (int i = row; i < row + size; i++) {
            for (int j = col; j < col + size; j++) {
                if (grid[i][j] != firstVal) {
                    isHomogeneous = false;
                    break;
                }
            }
            if (!isHomogeneous) {
                break;
            }
        }

        if (isHomogeneous) {
            return new Node(firstVal == 1, true, null, null, null, null);
        } else {
            int newSize = size / 2;
            Node topLeft = build(grid, row, col, newSize);
            Node topRight = build(grid, row, col + newSize, newSize);
            Node bottomLeft = build(grid, row + newSize, col, newSize);
            Node bottomRight = build(grid, row + newSize, col + newSize, newSize);
            // The 'val' for an internal node can be arbitrary, e.g., true.
            return new Node(true, false, topLeft, topRight, bottomLeft, bottomRight);
        }
    }
}
```
### Algorithm
- Create a recursive helper function `build(grid, row, col, size)`.
- In the helper function, check if the sub-grid from `(row, col)` of `size x size` is homogeneous.
- To check for homogeneity, iterate through all `size * size` cells and compare them to the first cell's value.
- If the sub-grid is homogeneous, create and return a leaf node with `isLeaf=true` and `val` set to the common value.
- If the sub-grid is not homogeneous, create an internal node with `isLeaf=false`.
- Recursively call `build` for the four quadrants:
    - `topLeft = build(grid, row, col, size/2)`
    - `topRight = build(grid, row, col + size/2, size/2)`
    - `bottomLeft = build(grid, row + size/2, col, size/2)`
    - `bottomRight = build(grid, row + size/2, col + size/2, size/2)`
- Assign the results to the children of the internal node and return it.
- The initial call is `construct(grid)` which calls `build(grid, 0, 0, grid.length)`.

## Recursive Approach with Prefix Sums
This approach improves upon the naive recursive solution by optimizing the homogeneity check. The key bottleneck is repeatedly scanning sub-grids to see if they contain all the same values. We can pre-compute a 2D prefix sum array (also known as an integral image) of the grid. This allows us to find the sum of any rectangular sub-grid in `O(1)` time. A sub-grid is homogeneous if its sum is either 0 (all 0s) or equal to its area (all 1s).
**Time:** O(N^2). The pre-computation of the prefix sum array takes `O(N^2)`. The recursive construction involves visiting each node of the Quad Tree once. The work done at each node is `O(1)`. In the worst case, the tree has `O(N^2)` nodes. Thus, the recursion takes `O(N^2)` time. The total time complexity is `O(N^2) + O(N^2) = O(N^2)`. · **Space:** O(N^2). We need `O(N^2)` space for the prefix sum array. The Quad Tree itself can also take up to `O(N^2)` space. The recursion stack uses `O(log N)` space.
**Pros:** Much more efficient than the naive approach, with an optimal time complexity of `O(N^2)`.; The logic remains recursive and relatively easy to follow.
**Cons:** Requires extra space of `O(N^2)` for the prefix sum array.
### Explanation
The overall structure is still a recursive function `build(row, col, size)`, but the way it checks for homogeneity is different and much faster.

1.  **Pre-computation:** First, we create a prefix sum array, `prefixSum`, of size `(n+1) x (n+1)`. `prefixSum[i+1][j+1]` will store the sum of all elements in the rectangle from `(0, 0)` to `(i, j)` in the original `grid`. This can be computed in `O(n^2)` time.

2.  **Optimized Homogeneity Check:** With the `prefixSum` array, we can calculate the sum of any `size x size` sub-grid starting at `(row, col)` in `O(1)`. The sum is given by:
    `subgridSum = prefixSum[row+size][col+size] - prefixSum[row][col+size] - prefixSum[row+size][col] + prefixSum[row][col]`.
    - If `subgridSum == 0`, all elements are 0.
    - If `subgridSum == size * size`, all elements are 1.
    - Otherwise, the sub-grid contains mixed values.

3.  **Recursive Construction:** The rest of the logic is the same as the naive approach. If the sub-grid is homogeneous, create a leaf node. Otherwise, create an internal node and recurse on the four quadrants. Since the check is now `O(1)`, the performance is significantly better.

```java
class Solution {
    int[][] prefixSum;
    int[][] grid;

    public Node construct(int[][] grid) {
        int n = grid.length;
        this.grid = grid;
        this.prefixSum = new int[n + 1][n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                prefixSum[i + 1][j + 1] = grid[i][j] + prefixSum[i][j + 1] + prefixSum[i + 1][j] - prefixSum[i][j];
            }
        }
        return build(0, 0, n);
    }

    private Node build(int row, int col, int size) {
        int sum = prefixSum[row + size][col + size] - prefixSum[row][col + size] - prefixSum[row + size][col] + prefixSum[row][col];

        if (sum == 0) { // All 0s
            return new Node(false, true, null, null, null, null);
        } else if (sum == size * size) { // All 1s
            return new Node(true, true, null, null, null, null);
        } else { // Mixed values
            int newSize = size / 2;
            Node topLeft = build(row, col, newSize);
            Node topRight = build(row, col + newSize, newSize);
            Node bottomLeft = build(row + newSize, col, newSize);
            Node bottomRight = build(row + newSize, col + newSize, newSize);
            return new Node(true, false, topLeft, topRight, bottomLeft, bottomRight);
        }
    }
}
```
### Algorithm
- Pre-compute a 2D prefix sum array `prefixSum` for the input `grid`. This takes `O(N^2)` time.
- Create a recursive helper function `build(row, col, size)`.
- In the helper function, calculate the sum of the current `size x size` sub-grid using the `prefixSum` array in `O(1)` time.
- Check if the sum is `0` (all zeros) or `size * size` (all ones).
- If the sub-grid is homogeneous, create and return a leaf node.
- If not, create an internal node, recursively call `build` for the four quadrants, assign the children, and return the node.
- The initial call is `construct(grid)` which first builds the prefix sum array and then calls `build(0, 0, grid.length)`.

## Optimized Post-order Recursive Approach
This approach is also recursive but optimizes the process by avoiding both redundant grid scans and the need for an auxiliary prefix sum array. It works in a bottom-up fashion (similar to a post-order traversal). The recursive function builds the tree for the sub-quadrants first and then uses the results to decide whether to create a leaf or an internal node for the current grid.
**Time:** O(N^2). The recurrence relation is `T(N) = 4 * T(N/2) + O(1)`, which resolves to `O(N^2)`. We visit each cell of the grid once at the base case of the recursion (`size == 1`), and the merge/check operations at each internal node take constant time. · **Space:** O(N^2). The space is dominated by the storage for the Quad Tree itself, which can have `O(N^2)` nodes in the worst case. The recursion stack depth is `O(log N)`. This approach does not require any auxiliary `O(N^2)` data structure.
**Pros:** Achieves optimal `O(N^2)` time complexity.; More space-efficient than the prefix sum approach as it avoids the `O(N^2)` auxiliary array.
**Cons:** The logic can be slightly more complex to reason about compared to the top-down approaches.
### Explanation
The recursive function, let's call it `build(row, col, size)`, will construct and return the node for the sub-grid starting at `(row, col)` of `size x size`.

The logic is as follows:
1.  **Base Case:** If `size == 1`, the sub-grid is a single cell. We are at the lowest level of recursion. We create a leaf node with `isLeaf = true` and `val` corresponding to `grid[row][col]`. This node is returned.
2.  **Recursive Step:** If `size > 1`, we first recursively call `build` for the four sub-quadrants.
3.  **Merge Check:** After the recursive calls return, we inspect the four children nodes. If all four children are leaf nodes (`isLeaf == true`) and they all have the same `val`, it means the current `size x size` grid is homogeneous. In this case, we can "merge" them. We create a single new leaf node with the common value and return it. The four sub-trees that were just created are effectively discarded.
4.  **Internal Node Creation:** If the four children cannot be merged (either because one of them is not a leaf or they don't all have the same value), it means the current grid is not homogeneous. We create a new internal node (`isLeaf = false`), assign the four children nodes we received from the recursive calls, and return this new internal node.

This post-order traversal style ensures that we only ever create nodes that are necessary for the final tree, and the homogeneity check is implicitly done by checking the returned children.

```java
class Solution {
    int[][] grid;

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

    private Node build(int row, int col, int size) {
        if (size == 1) {
            return new Node(grid[row][col] == 1, true, null, null, null, null);
        }

        int newSize = size / 2;
        Node topLeft = build(row, col, newSize);
        Node topRight = build(row, col + newSize, newSize);
        Node bottomLeft = build(row + newSize, col, newSize);
        Node bottomRight = build(row + newSize, col + newSize, newSize);

        // Check if all children are leaves and have the same value
        if (topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf &&
            topLeft.val == topRight.val && topRight.val == bottomLeft.val && bottomLeft.val == bottomRight.val) {
            // Merge them into a single leaf node
            return new Node(topLeft.val, true, null, null, null, null);
        } else {
            // Otherwise, create an internal node
            return new Node(true, false, topLeft, topRight, bottomLeft, bottomRight);
        }
    }
}
```
### Algorithm
- Create a recursive helper function `build(grid, row, col, size)`.
- The base case for the recursion is when `size == 1`. In this case, return a leaf node representing the single cell.
- For `size > 1`, recursively call `build` for the four quadrants to get the four children nodes.
- After the recursive calls return, check if the four returned nodes are all leaf nodes and if they all share the same `val`.
- If they do, it means the current grid is homogeneous. Return a new single leaf node with that common value.
- Otherwise, the current grid is not homogeneous. Return a new internal node, setting its four children to the nodes returned by the recursive calls.
- The initial call is `construct(grid)` which calls `build(grid, 0, 0, grid.length)`.

# Solutions
### Java

```java
/* // 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; } 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 { public Node construct ( int [][] grid ) { return dfs ( 0 , 0 , grid . length - 1 , grid [ 0 ]. length - 1 , grid ); } private Node dfs ( int a , int b , int c , int d , int [][] grid ) { int zero = 0 , one = 0 ; for ( int i = a ; i <= c ; ++ i ) { for ( int j = b ; j <= d ; ++ j ) { if ( grid [ i ][ j ] == 0 ) { zero = 1 ; } else { one = 1 ; } } } boolean isLeaf = zero + one == 1 ; boolean val = isLeaf && one == 1 ; Node node = new Node ( val , isLeaf ); if ( isLeaf ) { return node ; } node . topLeft = dfs ( a , b , ( a + c ) / 2 , ( b + d ) / 2 , grid ); node . topRight = dfs ( a , ( b + d ) / 2 + 1 , ( a + c ) / 2 , d , grid ); node . bottomLeft = dfs (( a + c ) / 2 + 1 , b , c , ( b + d ) / 2 , grid ); node . bottomRight = dfs (( a + c ) / 2 + 1 , ( b + d ) / 2 + 1 , c , d , grid ); return node ; } }
```

### CPP

```cpp
/* // 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; } Node(bool _val, bool _isLeaf) { val = _val; isLeaf = _isLeaf; topLeft = NULL; topRight = NULL; bottomLeft = NULL; bottomRight = NULL; } Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) { val = _val; isLeaf = _isLeaf; topLeft = _topLeft; topRight = _topRight; bottomLeft = _bottomLeft; bottomRight = _bottomRight; } }; */ class Solution { public: Node * construct ( vector < vector < int >>& grid ) { return dfs ( 0 , 0 , grid . size () - 1 , grid [ 0 ]. size () - 1 , grid ); } Node * dfs ( int a , int b , int c , int d , vector < vector < int >>& grid ) { int zero = 0 , one = 0 ; for ( int i = a ; i <= c ; ++ i ) { for ( int j = b ; j <= d ; ++ j ) { if ( grid [ i ][ j ]) one = 1 ; else zero = 1 ; } } bool isLeaf = zero + one == 1 ; bool val = isLeaf && one ; Node * node = new Node ( val , isLeaf ); if ( isLeaf ) return node ; node -> topLeft = dfs ( a , b , ( a + c ) / 2 , ( b + d ) / 2 , grid ); node -> topRight = dfs ( a , ( b + d ) / 2 + 1 , ( a + c ) / 2 , d , grid ); node -> bottomLeft = dfs (( a + c ) / 2 + 1 , b , c , ( b + d ) / 2 , grid ); node -> bottomRight = dfs (( a + c ) / 2 + 1 , ( b + d ) / 2 + 1 , c , d , grid ); return node ; } };
```

### Python

```python
""" # 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 dfs ( a , b , c , d ): zero = one = 0 for i in range ( a , c + 1 ): for j in range ( b , d + 1 ): if grid [ i ][ j ] == 0 : zero = 1 else : one = 1 isLeaf = zero + one == 1 val = isLeaf and one if isLeaf : return Node ( grid [ a ][ b ], True ) topLeft = dfs ( a , b , ( a + c ) // 2 , ( b + d ) // 2 ) topRight = dfs ( a , ( b + d ) // 2 + 1 , ( a + c ) // 2 , d ) bottomLeft = dfs (( a + c ) // 2 + 1 , b , c , ( b + d ) // 2 ) bottomRight = dfs (( a + c ) // 2 + 1 , ( b + d ) // 2 + 1 , c , d ) return Node ( val , isLeaf , topLeft , topRight , bottomLeft , bottomRight ) return dfs ( 0 , 0 , len ( grid ) - 1 , len ( grid [ 0 ]) - 1 )
```