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

# Logical OR of Two Binary Grids Represented as

> Tested Python solution for LeetCode 558 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 558, [Medium](/catalog/medium). Topics: [Divide and Conquer](/catalog/topics/divide-and-conquer), [Tree](/catalog/topics/tree). [View on LeetCode](https://leetcode.com/problems/logical-or-of-two-binary-grids-represented-as-quad-trees/description/).

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

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

## Problem

A Binary Matrix is a matrix in which all the elements are either `0` or `1`.

Given `quadTree1` and `quadTree2`. `quadTree1` represents a `n * n` binary matrix and `quadTree2` represents another `n * n` binary matrix.

Return *a Quad-Tree* representing the `n * n` binary matrix which is the result of **logical bitwise OR** of the two binary matrixes represented by `quadTree1` and `quadTree2`.

Notice that you can assign the value of a node to **True** or **False** when `isLeaf` is **False**, and both are **accepted** in the answer.

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.
* `isLeaf`: True if the node is leaf node on the tree or False if the node has the 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 divide illustration](https://assets.leetcode.com/uploads/2020/02/11/new_top.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:** The input/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 a 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**.

### Examples

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

```
Input: quadTree1 = [[0,1],[1,1],[1,1],[1,0],[1,0]]
, quadTree2 = [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
Output: [[0,0],[1,1],[1,1],[1,1],[1,0]]
Explanation: quadTree1 and quadTree2 are shown above. You can see the binary matrix which is represented by each Quad-Tree.
If we apply logical bitwise OR on the two binary matrices we get the binary matrix below which is represented by the result Quad-Tree.
Notice that the binary matrices shown are only for illustration, you don't have to construct the binary matrix to get the result tree.
```

![Result matrix](https://assets.leetcode.com/uploads/2020/02/11/qtr.png)

```
Input: quadTree1 = [[1,0]], quadTree2 = [[1,0]]
Output: [[1,0]]
Explanation: Each tree represents a binary matrix of size 1*1. Each matrix contains only zero.
The resulting matrix is of size 1*1 with also zero.
```

### Constraints

* quadTree1 and quadTree2 are both valid Quad-Trees each representing a `n * n` grid.
* `n == 2^x` where `0 <= x <= 9`.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/logical_or_of_two_binary_grids_represented_as_quad_trees/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/logical_or_of_two_binary_grids_represented_as_quad_trees/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)
    # Space: O(log n) recursion depth
    def intersect(self, quad_tree1: Node, quad_tree2: Node) -> Node:
        if quad_tree1.isLeaf:
            return Node(True, True) if quad_tree1.val else quad_tree2
        if quad_tree2.isLeaf:
            return Node(True, True) if quad_tree2.val else quad_tree1
        quadrants = (
            (quad_tree1.topLeft, quad_tree2.topLeft),
            (quad_tree1.topRight, quad_tree2.topRight),
            (quad_tree1.bottomLeft, quad_tree2.bottomLeft),
            (quad_tree1.bottomRight, quad_tree2.bottomRight),
        )
        merged: list[Node] = []
        for left, right in quadrants:
            assert left is not None and right is not None
            merged.append(self.intersect(left, right))
        if all(child.isLeaf and child.val for child in merged):
            return Node(True, True)
        top_left, top_right, bottom_left, bottom_right = merged
        return Node(False, False, top_left, top_right, bottom_left, bottom_right)
```

## Complexity

| Time | Space |
| - | - |
| O(n) | O(log n) recursion depth |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.