> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Construct Quad Tree Python Solution with Tests

> Tested Python solution for LeetCode 427 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 427, Medium. Topics: Array, Divide and Conquer, Tree, Matrix. [View on LeetCode](https://leetcode.com/problems/construct-quad-tree/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 427   # by problem number
lcpy gen -s construct_quad_tree   # by problem name
```

## 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.

**Quad-Tree format:** 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. The node is represented as a list `[isLeaf, val]`.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2020/02/11/grid1.png)

```
Input: grid = [[0,1],[1,0]]
Output: [[0,1],[1,0],[1,1],[1,1],[1,0]]
Explanation: The root is not a leaf. Its four children (top-left, top-right, bottom-left, bottom-right) are leaves.
```

![Example 2](https://assets.leetcode.com/uploads/2020/02/12/e2mat.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]]
```

### Constraints

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

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/construct_quad_tree/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/construct_quad_tree/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from __future__ import annotations


# ruff: noqa: N803
class Node:
    def __init__(
        self,
        val: bool,
        isLeaf: bool,
        topLeft: Node | None = None,
        topRight: Node | None = None,
        bottomLeft: Node | None = None,
        bottomRight: Node | None = None,
    ) -> None:
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight


class Solution:
    # Time: O(n^2) every cell visited once per level, log n levels
    # Space: O(log n) recursion depth (tree height)
    def construct(self, grid: list[list[int]]) -> Node:
        def build(row: int, col: int, size: int) -> Node:
            first = grid[row][col]
            uniform = True
            for r in range(row, row + size):
                for c in range(col, col + size):
                    if grid[r][c] != first:
                        uniform = False
                        break
                if not uniform:
                    break
            if uniform:
                return Node(val=bool(first), isLeaf=True)
            half = size // 2
            return Node(
                val=True,
                isLeaf=False,
                topLeft=build(row, col, half),
                topRight=build(row, col + half, half),
                bottomLeft=build(row + half, col, half),
                bottomRight=build(row + half, col + half, half),
            )

        return build(0, 0, len(grid))
```

## Complexity

| Time                                                   | Space                                  |
| ------------------------------------------------------ | -------------------------------------- |
| O(n^2) every cell visited once per level, log n levels | O(log n) recursion depth (tree height) |

## Tags

[NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).