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'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.isLeaf to False and set val to any value and divide the current grid into four sub-grids as shown in the photo.
If you want to know more about the Quad-Tree, you can refer to the wiki.
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:
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.
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.Problem Overview: Two binary grids are compressed using quad-trees. Each node represents a region that is either entirely 0, entirely 1, or subdivided into four children. Your task is to compute the logical OR of the two grids and return the resulting quad-tree structure.
Approach 1: Recursive Merge of Quad-Trees (O(n) time, O(h) space)
This approach applies divide and conquer. You recursively merge corresponding nodes from both trees. If either node is a leaf with value 1, the result is immediately a leaf 1 because the OR operation dominates the region. If both nodes are leaves with value 0, the result is a leaf 0. Otherwise recursively merge the four quadrants: topLeft, topRight, bottomLeft, and bottomRight. After recursion, check if all four children become identical leaf nodes; if so, compress them into a single leaf node. This keeps the resulting tree minimal while maintaining correctness.
Approach 2: Iterative Post-Order Traversal Using Stack (O(n) time, O(n) space)
This version avoids recursion by simulating the traversal with an explicit stack. Each stack entry holds a pair of nodes from the two input trees and tracks whether their children have been processed. The algorithm pushes child pairs first (post-order style), computes their merged results, and then combines them into the parent node. Just like the recursive method, if either node is a leaf with value 1, you short‑circuit and return a leaf 1. If all four merged children are leaf nodes with the same value, compress them into a single leaf node to maintain the quad-tree property. This approach is useful when recursion depth could be large or when you want tighter control over traversal state.
Recommended for interviews: The recursive merge is the expected solution. It directly mirrors the quad-tree structure and clearly demonstrates understanding of recursion and divide‑and‑conquer patterns. The iterative stack solution shows deeper mastery of traversal mechanics and can help in environments where recursion depth is constrained.
This approach involves recursively merging the quad-trees using a depth-first traversal. When encountering a leaf node in one tree, we can determine the result for that section of the grid based on the leaf's value and the corresponding part in the other tree. If both nodes are not leaf nodes, you recursively merge all four children.
This function recursively merges two quad-trees. If one of them is a leaf, it checks whether to return the leaf node or recurse further. When not leaves, it recurses into all children nodes and merges them.
Time Complexity: O(n^2), where n is the size of the matrix.
Space Complexity: O(log(n)), due to the recursion stack.
This solution is designed with an iterative method that employs a post-order traversal of the trees using a stack. This can help avoid recursion depth issues in Python or other environments that could encounter recursion limits.
In C#, the design is equivalent in recognizing leaf-node similarities and differences between sections of the grid and using them to construct merged nodes iteratively.
C#
JavaScript
Time Complexity: O(n^2), where n is the size of the matrix.
Space Complexity: Depends on the implementation; using a stack can remain O(log n).
| Approach | Complexity |
|---|---|
| Recursive Merge of Quad-Trees | Time Complexity: O(n^2), where n is the size of the matrix. |
| Iterative Post-Order Traversal Using Stack | Time Complexity: O(n^2), where n is the size of the matrix. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Merge of Quad-Trees | O(n) | O(h) | General case; simplest and most interview-friendly solution |
| Iterative Post-Order Traversal Using Stack | O(n) | O(n) | When avoiding recursion or managing deep quad-tree structures |
LeetCode 558 - Logical OR of Two Binary Grids Represented as Quad-Trees • Light Of Truth • 412 views views
Watch 5 more video solutions →Practice Logical OR of Two Binary Grids Represented as Quad-Trees with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor