Logical Or Of Two Binary Grids Represented As Quad Trees - Leetcode Solution

Problem statement:

Given two binary grids represented as Quad Trees, return the Quad Tree representing the logical OR of the two grids.

Notice that you can assign the value True or False to a node in the Quad Tree, and this value will apply to all of the node's children. A node is a leaf node if and only if it has the value True or False.

A Quad Tree is a tree data structure in which each internal node has exactly four children: topLeft, topRight, bottomLeft, and bottomRight. Quad trees are often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions.

Example:

Input: quadTree1 = [[0,1],[1,1],[1,1],[1,0],[1,0]] quadTree2 = [[0,0],[1,1],[1,1],[1,0],[1,0]] Output: [[0,0],[0,1],[1,1],[1,0],[1,0]]

Explanation: quadTree1 and quadTree2 are shown above. The logical OR of the two trees is [0,0],[0,1],[1,1],[1,0],[1,0].

Solution:

To solve the given problem, we can make use of a recursive approach where we will traverse the Quad Trees and perform a logical OR operation on corresponding nodes to create a new Quad Tree that represents the logical OR of the two given Quad Trees.

At each node, we first check if the corresponding nodes in the two Quad Trees are both leaf nodes i.e. they have True or False value. If so, we simply perform the logical OR operation on them and create a new node in the resulting Quad Tree representing their OR value.

If at least one node doesn't have a leaf node value, we recursively perform the logic on each of its corresponding children nodes.

When we encounter a leaf node, we will create a new node in the resulting Quad Tree representing the value of the leaf node. The base condition for the recursion will be when both the corresponding nodes in the two Quad Trees are leaf nodes.

Algorithm:

The steps to implement the recursive algorithm for the given problem are as follows:

1. Define a function that takes two Quad Trees as input and returns a new Quad Tree representing their logical OR.

2. Check if both the input Quad Trees are leaf nodes. a. If so, perform the logical OR on the corresponding nodes and create a new node for the resulting Quad Tree. b. If not, recursively perform the logical OR on each of the corresponding child nodes of both the input Quad Trees.

3. Create a new node for the resulting Quad Tree representing the node value of the leaf node encountered.

4. Return the new Quad Tree obtained as a result of the above steps.

Python Code:

The Python code implementing the above algorithm is as follows:

# 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':
        if quadTree1.isLeaf:
            return quadTree1 if quadTree1.val else quadTree2
        
        if quadTree2.isLeaf:
            return quadTree2 if quadTree2.val else quadTree1
        
        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 topLeft.isLeaf and topRight.isLeaf and bottomLeft.isLeaf and bottomRight.isLeaf and \
        topLeft.val == topRight.val == bottomLeft.val == bottomRight.val:
            return Node(topLeft.val, True, None, None, None, None)
        
        return Node(False, False, topLeft, topRight, bottomLeft, bottomRight)

The above code implements the recursive solution to the given problem using a helper function 'intersect'. The 'intersect' function takes two Quad Trees as input and returns a new Quad Tree that represents their logical OR.

Firstly, we check if the nodes in both the input Quad Trees are leaf nodes. If so, we perform the logical OR operation on the corresponding nodes and create a new node in the resulting Quad Tree representing their OR value.

Otherwise, we recursively perform the logic on each of the corresponding child nodes of both the input Quad Trees.

When we encounter a leaf node, we create a new node in the resulting Quad Tree representing the value of the leaf node. The base condition for the recursion is when both the corresponding nodes in the two input Quad Trees are leaf nodes.

After the recursion completes, we return the new Quad Tree that represents the logical OR of the two given Quad Trees.

1