# Logical OR of Two Binary Grids Represented as Quad-Trees
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/logical-or-of-two-binary-grids-represented-as-quad-trees)
Canonical: https://scaleengineer.com/dsa/problems/logical-or-of-two-binary-grids-represented-as-quad-trees
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer)
**Data structures:** Tree
---
## 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.
![](https://assets.glich.co/dsa/logical-or-of-two-binary-grids-represented-as-quad-trees/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:**

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 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/logical-or-of-two-binary-grids-represented-as-quad-trees/image1.png) ![](https://assets.glich.co/dsa/logical-or-of-two-binary-grids-represented-as-quad-trees/image2.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.
![](https://assets.glich.co/dsa/logical-or-of-two-binary-grids-represented-as-quad-trees/image3.png)

**Example 2:**

**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 == 2x` where `0 <= x <= 9`.

# Approaches
## Brute-Force: Convert to Grid, Compute OR, Convert Back
This approach is straightforward but inefficient. It involves three main steps: first, convert both input Quad-Trees into their corresponding `n x n` binary matrices. Second, perform a cell-by-cell logical OR operation on these two matrices to produce a result matrix. Finally, construct a new Quad-Tree from this result matrix. This method is easy to understand but can be slow and memory-intensive, especially for large grids, as it doesn't leverage the compressed nature of Quad-Trees.
**Time:** O(n^2) - Converting a Quad-Tree to a grid takes `O(n^2)`. Performing the logical OR on two `n x n` grids takes `O(n^2)`. Building a Quad-Tree from a grid takes `O(n^2)`. The total complexity is `O(n^2) + O(n^2) + O(n^2) = O(n^2)`. · **Space:** O(n^2) - We need to store at least two `n x n` grids, requiring `O(n^2)` space. The result grid also takes `O(n^2)` space.
**Pros:** Conceptually simple and easy to follow.; Breaks the problem down into three distinct, well-understood subproblems.
**Cons:** Highly inefficient in terms of both time and space.; Requires `O(n^2)` space for the grids, which can be very large for `n` up to 512.; Time complexity is `O(n^2)`, which is slow for large `n`.; It completely ignores the compression benefit of using Quad-Trees, which is their primary purpose.
### Explanation
The algorithm consists of three main parts:

1.  **`convertToGrid(Node root, int n)`**: A function to transform a Quad-Tree into a 2D grid. It would internally use a recursive helper `fillGrid(Node node, int r, int c, int size, boolean[][] grid)`. If `node` is a leaf, it fills the `size x size` subgrid starting at `(r, c)` with `node.val`. If it's not a leaf, it divides the current `size x size` area into four `size/2 x size/2` quadrants and recursively calls itself for each child node on the corresponding quadrant.
2.  **`performOR(grid1, grid2)`**: A function that takes two grids and returns a new grid which is the logical OR of the two. It iterates through each cell `(i, j)` and computes `result[i][j] = grid1[i][j] || grid2[i][j]`.
3.  **`buildTree(grid, r, c, size)`**: A recursive function to build a Quad-Tree from a 2D grid. It first checks if the `size x size` subgrid starting at `(r, c)` is uniform (all 0s or all 1s). This check takes `O(size^2)` time. If uniform, it returns a leaf node. If not, it creates an internal node and recursively calls itself for the four sub-quadrants to build the child nodes.

The main function would orchestrate these steps. Note that this approach is generally not recommended due to its poor performance.

```java
// Conceptual implementation of the buildTree helper
private Node buildTree(boolean[][] grid, int r, int c, int size) {
    // Check if the subgrid is uniform
    boolean isUniform = true;
    boolean firstVal = grid[r][c];
    for (int i = r; i < r + size; i++) {
        for (int j = c; j < c + size; j++) {
            if (grid[i][j] != firstVal) {
                isUniform = false;
                break;
            }
        }
        if (!isUniform) break;
    }

    if (isUniform) {
        return new Node(firstVal, true, null, null, null, null);
    } else {
        int newSize = size / 2;
        Node topLeft = buildTree(grid, r, c, newSize);
        Node topRight = buildTree(grid, r, c + newSize, newSize);
        Node bottomLeft = buildTree(grid, r + newSize, c, newSize);
        Node bottomRight = buildTree(grid, r + newSize, c + newSize, newSize);
        return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
    }
}
```
### Algorithm
1.  **Convert Quad-Tree to Grid:** Create a helper function that recursively traverses a Quad-Tree and populates a 2D boolean grid. For a leaf node, it fills the corresponding grid area with the node's value. For an internal node, it recurses on its four children for the four sub-quadrants.
2.  **Get Grids:** Call the conversion function for both `quadTree1` and `quadTree2` to obtain `grid1` and `grid2`. This step requires knowing the grid dimension `n`.
3.  **Perform Logical OR:** Create a new `resultGrid` of size `n x n`. Iterate through every cell `(i, j)` and compute `resultGrid[i][j] = grid1[i][j] || grid2[i][j]`.
4.  **Convert Grid to Quad-Tree:** Create another helper function that recursively builds a Quad-Tree from a grid. For a given grid area, it first checks if all cells have the same value. If so, it creates a leaf node. Otherwise, it creates an internal node and recursively calls itself on the four sub-quadrants.
5.  **Return Result:** Call the grid-to-tree conversion function on `resultGrid` to get the final Quad-Tree.

## Efficient Recursive Traversal
This approach performs a recursive traversal on both Quad-Trees simultaneously. It constructs the resulting Quad-Tree directly without the need for an intermediate grid representation. The logic cleverly utilizes the properties of the logical OR operation (`A OR 1 = 1`, `A OR 0 = A`) and the structure of the Quad-Tree to prune the traversal and merge nodes, leading to a highly efficient solution.
**Time:** O(N1 + N2) - where `N1` and `N2` are the number of nodes in `quadTree1` and `quadTree2` respectively. In the worst case, we might visit every node in both trees. Each recursive call involves a constant amount of work, so the time is proportional to the number of nodes visited. · **Space:** O(N1 + N2) - The space is used for the recursion stack and the new tree being built. The recursion depth is at most `log(n)`, so stack space is `O(log n)`. The space for the new tree is proportional to its number of nodes, which is at most `O(N1 + N2)`. Thus, the total space is `O(N1 + N2)`.
**Pros:** Highly efficient, especially for grids with large uniform areas.; Avoids the overhead of creating and processing large intermediate matrices.; Time and space complexity are proportional to the number of nodes in the trees, not the size of the grid.
**Cons:** The recursive logic can be slightly more complex to grasp initially compared to the brute-force method.
### Explanation
The core of this approach is a recursive function, `intersect(node1, node2)`, which computes the Quad-Tree node for the logical OR of the regions represented by `node1` and `node2`.

The recursion follows these rules:
- **Pruning with Leaf Nodes:** If one of the nodes, say `node1`, is a leaf, we can quickly determine the result. If `node1.val` is `true` (a grid of 1s), the OR result is also a grid of 1s, so we return a new leaf node with `val = true`. If `node1.val` is `false` (a grid of 0s), the OR result is identical to the grid represented by `node2`, so we can simply return `node2`.
- **Recursive Descent:** If both `node1` and `node2` are internal nodes, we must recurse deeper. We call `intersect` on each pair of corresponding children (`topLeft` with `topLeft`, `topRight` with `topRight`, etc.).
- **Merging Children:** After the four recursive calls for the children return, we check if the resulting four sub-trees can be merged. If all four are leaf nodes and share the same value, they represent a uniform quadrant. We can merge them by creating a single new leaf node with that common value. Otherwise, we create a new internal node and assign the four sub-trees as its children.

This process efficiently builds the result tree from the bottom up, merging quadrants whenever possible.

```java
class Solution {
    public Node intersect(Node quadTree1, Node quadTree2) {
        // If quadTree1 is a leaf node
        if (quadTree1.isLeaf) {
            // If its value is true (1), the OR result is a leaf with value true.
            if (quadTree1.val) {
                return new Node(true, true, null, null, null, null);
            }
            // If its value is false (0), the OR result is simply quadTree2.
            return quadTree2;
        }

        // If quadTree2 is a leaf node (symmetric case)
        if (quadTree2.isLeaf) {
            if (quadTree2.val) {
                return new Node(true, true, null, null, null, null);
            }
            return quadTree1;
        }

        // If both are internal nodes, recurse on their children
        Node tl = intersect(quadTree1.topLeft, quadTree2.topLeft);
        Node tr = intersect(quadTree1.topRight, quadTree2.topRight);
        Node bl = intersect(quadTree1.bottomLeft, quadTree2.bottomLeft);
        Node br = intersect(quadTree1.bottomRight, quadTree2.bottomRight);

        // Check if all children are leaves and have the same value to merge them
        if (tl.isLeaf && tr.isLeaf && bl.isLeaf && br.isLeaf &&
            tl.val == tr.val && tr.val == bl.val && bl.val == br.val) {
            // If so, merge them into a single leaf node
            return new Node(tl.val, true, null, null, null, null);
        } else {
            // Otherwise, create a new internal node with these children
            return new Node(false, false, tl, tr, bl, br);
        }
    }
}
```
### Algorithm
1.  Define a recursive function `intersect(node1, node2)` that returns the resulting `Node`.
2.  **Base Case 1:** If `node1` is a leaf (`node1.isLeaf == true`):
    - If `node1.val` is `true`, the OR operation results in a grid of all `true`. Return a new leaf node with `val = true`.
    - If `node1.val` is `false`, the OR operation result is determined by `node2`. Return `node2` itself.
3.  **Base Case 2:** If `node2` is a leaf, apply the symmetric logic from Base Case 1.
4.  **Recursive Step:** If both `node1` and `node2` are internal nodes (not leaves):
    - Recursively call `intersect` for each corresponding pair of children to get the four sub-tree results: `topLeft`, `topRight`, `bottomLeft`, `bottomRight`.
    - e.g., `topLeft = intersect(node1.topLeft, node2.topLeft)`
5.  **Merge Step:** After the recursive calls return, check if the four resulting children nodes can be merged. This is possible if all four are leaf nodes and all have the same `val`.
    - If they can be merged, return a new single leaf node with that common value.
    - Otherwise, return a new internal node with the four children nodes obtained from the recursive calls.
6.  The initial call to the function will be `intersect(quadTree1, quadTree2)`.

# 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() {} public Node(boolean _val,boolean _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 intersect ( Node quadTree1 , Node quadTree2 ) { return dfs ( quadTree1 , quadTree2 ); } private Node dfs ( Node t1 , Node t2 ) { if ( t1 . isLeaf && t2 . isLeaf ) { return new Node ( t1 . val || t2 . val , true ); } if ( t1 . isLeaf ) { return t1 . val ? t1 : t2 ; } if ( t2 . isLeaf ) { return t2 . val ? t2 : t1 ; } Node res = new Node (); res . topLeft = dfs ( t1 . topLeft , t2 . topLeft ); res . topRight = dfs ( t1 . topRight , t2 . topRight ); res . bottomLeft = dfs ( t1 . bottomLeft , t2 . bottomLeft ); res . bottomRight = dfs ( t1 . bottomRight , t2 . bottomRight ); boolean isLeaf = res . topLeft . isLeaf && res . topRight . isLeaf && res . bottomLeft . isLeaf && res . bottomRight . isLeaf ; boolean sameVal = res . topLeft . val == res . topRight . val && res . topRight . val == res . bottomLeft . val && res . bottomLeft . val == res . bottomRight . val ; if ( isLeaf && sameVal ) { res = res . topLeft ; } return res ; } }
```

### 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 * intersect ( Node * quadTree1 , Node * quadTree2 ) { return dfs ( quadTree1 , quadTree2 ); } Node * dfs ( Node * t1 , Node * t2 ) { if ( t1 -> isLeaf && t2 -> isLeaf ) return new Node ( t1 -> val || t2 -> val , true ); if ( t1 -> isLeaf ) return t1 -> val ? t1 : t2 ; if ( t2 -> isLeaf ) return t2 -> val ? t2 : t1 ; Node * res = new Node (); res -> topLeft = dfs ( t1 -> topLeft , t2 -> topLeft ); res -> topRight = dfs ( t1 -> topRight , t2 -> topRight ); res -> bottomLeft = dfs ( t1 -> bottomLeft , t2 -> bottomLeft ); res -> bottomRight = dfs ( t1 -> bottomRight , t2 -> bottomRight ); bool isLeaf = res -> topLeft -> isLeaf && res -> topRight -> isLeaf && res -> bottomLeft -> isLeaf && res -> bottomRight -> isLeaf ; bool sameVal = res -> topLeft -> val == res -> topRight -> val && res -> topRight -> val == res -> bottomLeft -> val && res -> bottomLeft -> val == res -> bottomRight -> val ; if ( isLeaf && sameVal ) res = res -> topLeft ; return res ; } };
```

### 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 intersect ( self , quadTree1 : "Node" , quadTree2 : "Node" ) -> "Node" : def dfs ( t1 , t2 ): if t1 . isLeaf and t2 . isLeaf : return Node ( t1 . val or t2 . val , True ) if t1 . isLeaf : return t1 if t1 . val else t2 if t2 . isLeaf : return t2 if t2 . val else t1 res = Node () res . topLeft = dfs ( t1 . topLeft , t2 . topLeft ) res . topRight = dfs ( t1 . topRight , t2 . topRight ) res . bottomLeft = dfs ( t1 . bottomLeft , t2 . bottomLeft ) res . bottomRight = dfs ( t1 . bottomRight , t2 . bottomRight ) isLeaf = ( res . topLeft . isLeaf and res . topRight . isLeaf and res . bottomLeft . isLeaf and res . bottomRight . isLeaf ) sameVal = ( res . topLeft . val == res . topRight . val == res . bottomLeft . val == res . bottomRight . val ) if isLeaf and sameVal : res = res . topLeft return res return dfs ( quadTree1 , quadTree2 )
```