# LeetCode 427: Construct Quad Tree

## Problem Restatement

We are given an `n x n` grid containing only `0` and `1`.

We need to build a quad tree that represents this grid.

A quad tree is a tree where each internal node has exactly four children:

| Child | Region |
|---|---|
| `topLeft` | upper-left quadrant |
| `topRight` | upper-right quadrant |
| `bottomLeft` | lower-left quadrant |
| `bottomRight` | lower-right quadrant |

Each node has two main fields:

| Field | Meaning |
|---|---|
| `val` | `True` for `1`, `False` for `0` |
| `isLeaf` | `True` if the node represents one uniform region |

If a square region contains only `0`s or only `1`s, it becomes a leaf node.

If a square region contains both `0` and `1`, we split it into four equal smaller squares and recursively build four child nodes.

For internal nodes, `val` can be either `True` or `False`; LeetCode accepts both. The important field for internal nodes is `isLeaf = False`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `grid`, an `n x n` binary matrix |
| Output | Root node of the quad tree |
| Cell values | Only `0` and `1` |
| Region split | Split non-uniform squares into four equal quadrants |

The node structure is usually:

```python
class Node:
    def __init__(
        self,
        val=False,
        isLeaf=False,
        topLeft=None,
        topRight=None,
        bottomLeft=None,
        bottomRight=None,
    ):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight
```

## Examples

Consider this grid:

```python
grid = [
    [1, 1],
    [1, 1],
]
```

The whole grid has the same value, so the result is one leaf node:

```text
Node(val=True, isLeaf=True)
```

No children are needed.

Now consider:

```python
grid = [
    [1, 0],
    [0, 1],
]
```

The whole grid is not uniform.

So we split it into four `1 x 1` regions:

```text
topLeft     = 1
topRight    = 0
bottomLeft  = 0
bottomRight = 1
```

Each `1 x 1` region is uniform, so each child is a leaf node.

The root is an internal node:

```text
Node(val=True, isLeaf=False)
```

with four children.

## First Thought: Check Every Region Directly

For any square region, we can check whether all cells have the same value.

Suppose the region starts at row `r`, column `c`, and has side length `size`.

We compare every cell in that region against:

```python
grid[r][c]
```

If every value is the same, we create a leaf node.

If at least one value differs, we split the region into four quadrants.

This is the natural recursive structure of the problem.

## Key Insight

The grid itself is already a square that can be recursively divided into four smaller squares.

So the core function should mean:

```python
build(r, c, size)
```

This builds the quad tree for the square region:

```text
rows    r to r + size - 1
columns c to c + size - 1
```

For each call:

1. Check whether the current square is uniform.
2. If uniform, return a leaf node.
3. Otherwise, split into four smaller squares of size `size // 2`.
4. Return an internal node with those four children.

This avoids copying subgrids. We pass only coordinates and size.

## Algorithm

Start with the full grid:

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

Inside `build(r, c, size)`:

Check whether all cells in the square have the same value as `grid[r][c]`.

If yes:

```python
return Node(grid[r][c] == 1, True)
```

Otherwise, compute:

```python
half = size // 2
```

Build the four children:

```python
topLeft = build(r, c, half)
topRight = build(r, c + half, half)
bottomLeft = build(r + half, c, half)
bottomRight = build(r + half, c + half, half)
```

Return an internal node:

```python
return Node(
    True,
    False,
    topLeft,
    topRight,
    bottomLeft,
    bottomRight,
)
```

The value `True` for an internal node is arbitrary. LeetCode accepts either value when `isLeaf` is `False`.

## Correctness

We prove the algorithm constructs the correct quad tree for every square region.

For a uniform region, all cells have the same value. The quad tree rule says such a region should be represented by one leaf node with `isLeaf = True` and `val` equal to that value. The algorithm checks all cells in the region and returns exactly that node.

For a non-uniform region, the quad tree rule says the region must be split into four equal quadrants. The algorithm computes `half = size // 2` and recursively builds the four required child regions: top-left, top-right, bottom-left, and bottom-right.

Each recursive call constructs the correct quad tree for its own smaller region by the same rule. The parent node then stores those four child trees and marks itself as an internal node with `isLeaf = False`.

The initial call covers the whole grid. Therefore, the returned root represents the entire input grid correctly.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2 log n)` | Each level may scan up to `n^2` cells, and there are `log n` split levels |
| Space | `O(log n)` | Recursion depth is the number of times the grid can be halved |

The output tree itself can contain many nodes. The table counts extra working space, excluding the returned tree.

In the worst case, many regions are non-uniform, so the algorithm scans cells repeatedly across multiple recursion levels.

## Implementation

```python
class Solution:
    def construct(self, grid: list[list[int]]) -> 'Node':
        n = len(grid)

        def is_uniform(r: int, c: int, size: int) -> bool:
            first = grid[r][c]

            for i in range(r, r + size):
                for j in range(c, c + size):
                    if grid[i][j] != first:
                        return False

            return True

        def build(r: int, c: int, size: int) -> 'Node':
            if is_uniform(r, c, size):
                return Node(grid[r][c] == 1, True)

            half = size // 2

            top_left = build(r, c, half)
            top_right = build(r, c + half, half)
            bottom_left = build(r + half, c, half)
            bottom_right = build(r + half, c + half, half)

            return Node(
                True,
                False,
                top_left,
                top_right,
                bottom_left,
                bottom_right,
            )

        return build(0, 0, n)
```

## Code Explanation

The public method starts with the full grid size:

```python
n = len(grid)
```

The helper `is_uniform` checks whether a square region contains only one value.

```python
first = grid[r][c]
```

This is the value every other cell must match.

The nested loops scan all cells inside the square:

```python
for i in range(r, r + size):
    for j in range(c, c + size):
```

If any value differs, the region needs to be split:

```python
if grid[i][j] != first:
    return False
```

The recursive function `build` constructs a quad tree node for one square region.

If the region is uniform, we return a leaf:

```python
return Node(grid[r][c] == 1, True)
```

The value must be boolean, so `grid[r][c] == 1` converts `1` to `True` and `0` to `False`.

If the region is not uniform, we split it:

```python
half = size // 2
```

Then we build each quadrant with the correct coordinates.

Top-left keeps the same starting point:

```python
build(r, c, half)
```

Top-right starts `half` columns to the right:

```python
build(r, c + half, half)
```

Bottom-left starts `half` rows below:

```python
build(r + half, c, half)
```

Bottom-right moves both down and right:

```python
build(r + half, c + half, half)
```

The returned internal node has `isLeaf = False`.

```python
return Node(True, False, top_left, top_right, bottom_left, bottom_right)
```

The `val` field is set to `True`, but for internal nodes that value does not matter.

## Testing

We can test by serializing the tree into a simple nested tuple format.

```python
class Node:
    def __init__(
        self,
        val=False,
        isLeaf=False,
        topLeft=None,
        topRight=None,
        bottomLeft=None,
        bottomRight=None,
    ):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight

def serialize(root):
    if root.isLeaf:
        return ("leaf", root.val)

    return (
        "node",
        serialize(root.topLeft),
        serialize(root.topRight),
        serialize(root.bottomLeft),
        serialize(root.bottomRight),
    )

def run_tests():
    s = Solution()

    root = s.construct([
        [1, 1],
        [1, 1],
    ])
    assert serialize(root) == ("leaf", True)

    root = s.construct([
        [0, 0],
        [0, 0],
    ])
    assert serialize(root) == ("leaf", False)

    root = s.construct([
        [1, 0],
        [0, 1],
    ])
    assert serialize(root) == (
        "node",
        ("leaf", True),
        ("leaf", False),
        ("leaf", False),
        ("leaf", True),
    )

    root = s.construct([
        [1],
    ])
    assert serialize(root) == ("leaf", True)

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| All `1`s | Whole grid becomes one leaf |
| All `0`s | Leaf value should be `False` |
| Mixed `2 x 2` grid | Root must split into four children |
| Single cell | Smallest possible region |