# LeetCode 558: Logical OR of Two Binary Grids Represented as Quad-Trees

## Problem Restatement

We are given two quad-trees representing two binary grids.

Each grid cell contains either:

| Value | Meaning |
|---|---|
| `0` | False |
| `1` | True |

We need to compute the logical OR of the two grids and return the result as a quad-tree.

The logical OR rule is:

| A | B | A OR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |

Each quad-tree node contains:

| Field | Meaning |
|---|---|
| `val` | Boolean value |
| `isLeaf` | Whether the node is a leaf |
| `topLeft` | Top-left child |
| `topRight` | Top-right child |
| `bottomLeft` | Bottom-left child |
| `bottomRight` | Bottom-right child |

A leaf node means the entire represented region has one uniform value.

The problem asks us to return a quad-tree representing the OR result. The statement guarantees both input trees represent grids of the same size. ([github.com](https://github.com/doocs/leetcode/blob/main/solution/0500-0599/0558.Logical%20OR%20of%20Two%20Binary%20Grids%20Represented%20as%20Quad-Trees/README_EN.md?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two quad-tree roots |
| Output | Root of the OR result quad-tree |
| Operation | Logical OR |
| Grid sizes | Same size |

Example function shape:

```python
def intersect(quadTree1: 'Node', quadTree2: 'Node') -> 'Node':
    ...
```

## Understanding Quad-Trees

A quad-tree recursively divides a square into four equal regions:

| Child | Region |
|---|---|
| `topLeft` | Upper-left |
| `topRight` | Upper-right |
| `bottomLeft` | Lower-left |
| `bottomRight` | Lower-right |

A leaf node represents a completely uniform region.

For example:

```python
isLeaf = True
val = 1
```

means the entire represented square is filled with `1`.

## First Thought: Rebuild the Entire Grid

One idea is:

1. Expand both quad-trees into full binary grids.
2. Compute the OR cell by cell.
3. Compress the result back into a quad-tree.

This works logically, but it wastes memory and ignores the compression already provided by quad-trees.

We should operate directly on the trees.

## Key Insight

Quad-trees already represent large uniform regions compactly.

Suppose one node is:

```python
isLeaf = True
val = 1
```

Then the entire region is all `1`.

For logical OR:

```python
1 OR anything = 1
```

So we can immediately return that node without exploring the other tree.

Similarly:

```python
0 OR x = x
```

So if a leaf node has value `0`, the result is exactly the other subtree.

This gives a recursive solution.

## Important Cases

### Case 1: First Node Is Leaf With Value `1`

```python
1 OR x = 1
```

Return the first node.

### Case 2: Second Node Is Leaf With Value `1`

```python
x OR 1 = 1
```

Return the second node.

### Case 3: First Node Is Leaf With Value `0`

```python
0 OR x = x
```

Return the second node.

### Case 4: Second Node Is Leaf With Value `0`

```python
x OR 0 = x
```

Return the first node.

### Case 5: Both Nodes Are Internal

Recursively OR the four children.

## Algorithm

For nodes `a` and `b`:

1. If `a` is a leaf:
   1. If `a.val == True`, return `a`.
   2. Otherwise return `b`.

2. If `b` is a leaf:
   1. If `b.val == True`, return `b`.
   2. Otherwise return `a`.

3. Recursively compute:
   ```python id="phnvt4"
   topLeft
   topRight
   bottomLeft
   bottomRight
   ```

4. After recursion, check whether all four children are leaves with the same value.
5. If yes, compress them into one leaf node.
6. Otherwise return an internal node containing those four children.

## Why Compression Is Needed

Suppose after recursion we get:

| Child | Value |
|---|---|
| topLeft | leaf `1` |
| topRight | leaf `1` |
| bottomLeft | leaf `1` |
| bottomRight | leaf `1` |

These four children together represent one uniform region.

Instead of keeping four separate nodes, we compress them into:

```python
isLeaf = True
val = 1
```

This keeps the tree minimal.

## Correctness

The algorithm follows the exact definition of logical OR.

If one node is a leaf with value `1`, then every cell in that represented region is `1`. Since:

```python
1 OR x = 1
```

the entire output region must also be all `1`. Returning that leaf is correct.

If one node is a leaf with value `0`, then:

```python
0 OR x = x
```

So the output region is exactly the other subtree. Returning the other subtree is correct.

When both nodes are internal, the represented regions are subdivided into four matching quadrants. The logical OR for the whole region is therefore obtained by computing the OR independently on each corresponding quadrant. The recursive calls correctly compute these four quadrant results.

After recursion, if all four children are leaves with the same value, then the whole region is uniform. Replacing those four leaves with one larger leaf preserves the represented grid exactly while producing a more compact quad-tree.

Therefore, every returned node represents exactly the logical OR of the corresponding regions in the two input trees.

## Complexity

Let `n` be the total number of nodes visited.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each relevant node pair is processed once |
| Space | `O(h)` | Recursive call stack height |

Here `h` is the maximum tree height.

In the worst case, all nodes may need to be explored.

## Implementation

```python
class Solution:
    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':
        if quadTree1.isLeaf:
            if quadTree1.val:
                return quadTree1
            return quadTree2

        if quadTree2.isLeaf:
            if quadTree2.val:
                return quadTree2
            return quadTree1

        topLeft = self.intersect(quadTree1.topLeft, quadTree2.topLeft)
        topRight = self.intersect(quadTree1.topRight, quadTree2.topRight)
        bottomLeft = self.intersect(quadTree1.bottomLeft, quadTree2.bottomLeft)
        bottomRight = self.intersect(quadTree1.bottomRight, quadTree2.bottomRight)

        children = [topLeft, topRight, bottomLeft, bottomRight]

        if (
            all(child.isLeaf for child in children)
            and topLeft.val == topRight.val == bottomLeft.val == bottomRight.val
        ):
            return Node(topLeft.val, True)

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

## Code Explanation

We first handle leaf shortcuts.

If the first tree is a leaf:

```python
if quadTree1.isLeaf:
```

and its value is `True`, then the OR result must also be `True` everywhere in that region:

```python
if quadTree1.val:
    return quadTree1
```

Otherwise, the first region is all `0`, so the result is just the second tree:

```python
return quadTree2
```

We do the symmetric logic for the second tree.

If both nodes are internal, we recursively combine corresponding children:

```python
topLeft = self.intersect(...)
```

After recursion, we check whether all children became identical leaf nodes:

```python
all(child.isLeaf for child in children)
```

and:

```python
topLeft.val == topRight.val == bottomLeft.val == bottomRight.val
```

If so, we compress them into one leaf node.

Otherwise, we return an internal node containing the four children.

## Testing

```python
def run_tests():
    s = Solution()

    # Leaf true OR leaf false -> true
    a = Node(True, True)
    b = Node(False, True)

    result = s.intersect(a, b)
    assert result.isLeaf is True
    assert result.val is True

    # Leaf false OR leaf false -> false
    a = Node(False, True)
    b = Node(False, True)

    result = s.intersect(a, b)
    assert result.isLeaf is True
    assert result.val is False

    # Leaf false OR internal -> internal
    internal = Node(
        False,
        False,
        Node(True, True),
        Node(False, True),
        Node(False, True),
        Node(True, True),
    )

    result = s.intersect(Node(False, True), internal)
    assert result.isLeaf is False

    print("all tests passed")
```

| Test | Why |
|---|---|
| `1 OR 0` | Immediate leaf shortcut |
| `0 OR 0` | Uniform false region |
| `0 OR internal` | Internal subtree should remain unchanged |
| Recursive internal cases | Checks recursive merging logic |
| Compression cases | Ensures identical children collapse into one leaf |