algoadvance

We are given two binary trees quadTree1 and quadTree2. These binary trees represent two binary grids in a compressed form using quad-trees. Each leaf node in a quad-tree represents a grid cell that can either be False (0) or True (1). The non-leaf nodes represent the subdivision of the grid into four quadrants.

Each node in the quad-tree has either four children or is a leaf node. The structure of a node in the quad-tree is defined as follows:

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

The task is to compute the logical OR of these two input binary grids, where the logical OR merges two grids into a bigger grid, setting each cell (i, j) to 1 if any cell (i, j) in either of the grids is 1.

The function should return the resulting quad-tree which represents the logical OR of both input grids.

Clarifying Questions

  1. Input Format:
    • Are quadTree1 and quadTree2 guaranteed to be valid quad-trees?
    • Can either of the input quad-trees be empty?
  2. Edge Cases:
    • How to handle when both quadTree1 and quadTree2 are leaves?
    • Will both trees always have the same size or depth?
  3. Output Format:
    • Should the output be a quad-tree of the same class Node?

Assuming standard input outputs based on quad-trees structure:

Strategy

  1. Leaf Node Evaluation:
    • If both nodes are leaves, the result is a leaf node whose value is the logical OR of the two given node values.
  2. Merge Cases:
    • If one node is a leaf and the other is not, we need to recursively apply the OR operation for the non-leaf node.
    • If neither node is a leaf, we recursively apply the OR operation to each quadrant.
  3. Optimization:
    • If after merging, all four children of a node are leaves with the same value, we can merge them into a single leaf node to keep the structure efficient.

Code Implementation

class Node:
    def __init__(self, val, isLeaf, topLeft=None, topRight=None, bottomLeft=None, bottomRight=None):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight

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

Time Complexity

This should provide a clear, concise solution to determine the logical OR of two quad-tree based binary grids.

Try our interview co-pilot at AlgoAdvance.com