Logical OR of Two Binary Grids Represented as Quad-Trees

This problem asks to perform a logical bitwise OR operation between two binary matrices represented by quad-trees and return a new quad-tree representing the resultant matrix. Here is how we can implement a solution for this in Python.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':
        # If either of the trees is a leaf and its value is True (1), the result is True (1)
        if quadTree1.isLeaf:
            return quadTree1 if quadTree1.val else quadTree2
        elif quadTree2.isLeaf:
            return quadTree2 if quadTree2.val else quadTree1
        
        # If neither of the trees is a leaf, recurse on their children
        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)

        # If all children are leaves and they have the same value, merge them into a single leaf
        if topLeft.isLeaf and topRight.isLeaf and bottomLeft.isLeaf and bottomRight.isLeaf:
            if topLeft.val == topRight.val == bottomLeft.val == bottomRight.val:
                return Node(topLeft.val, True, None, None, None, None)
        
        # Otherwise, create an internal node with these children
        return Node(False, False, topLeft, topRight, bottomLeft, bottomRight)

In the solution, we recursively intersect the corresponding children of quadTree1 and quadTree2. If at any point, we encounter a leaf node with value True (1), we return it directly, because any value OR’ed with 1 results in 1. If the leaf’s value is False (0), we return the other node, because any value OR’ed with 0 remains the same.

We keep doing this recursively until we have traversed all the children. If all children are leaves and have the same value, we merge them into a single leaf. If they’re not, we just create an internal node with these children.