Watch 6 video solutions for Logical OR of Two Binary Grids Represented as Quad-Trees, a medium level problem involving Divide and Conquer, Tree. This walkthrough by Light Of Truth has 412 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |