LeetCode 558: Logical OR of Two Binary Grids Represented as Quad-Trees Solution in Python – A Step-by-Step Guide

What Is LeetCode 558: Logical OR of Two Binary Grids Represented as Quad-Trees?

In LeetCode 558: Logical OR of Two Binary Grids Represented as Quad-Trees, you’re given two quad-trees quadTree1 and quadTree2, each representing an n x n binary grid (n is a power of 2), where each node is either a leaf (with a value of 0 or 1) or an internal node with four children (top-left, top-right, bottom-left, bottom-right). Your task is to return a quad-tree representing the logical OR of the two grids, where OR combines 0s and 1s (0 OR 0 = 0, 1 OR anything = 1). For example, merging two simple quad-trees might compress a grid like [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]] with another into a new quad-tree. This problem builds on LeetCode 427: Construct Quad Tree but focuses on merging operations.

Problem Statement

• Input: quadTree1, quadTree2 (Node)—two quad-trees representing binary grids.
• Output: Node—quad-tree representing logical OR of the grids.
• Rules: Leaf nodes have value 0 or 1; internal nodes have 4 children; OR operation applies to corresponding grid cells.

Constraints

• quadTree1 and quadTree2 represent n x n grids (n = 2^k, 0 ≤ k ≤ 9).
• Leaf nodes have isLeaf = True, value 0 or 1.
• Internal nodes have isLeaf = False, four child nodes.

Examples

• Input:
• quadTree1: Leaf(1,1), quadTree2: Leaf(1,0)
• Output: Leaf(1,1)
• OR of two 1x1 grids: 1 OR 0 = 1.
• Input:
• quadTree1: Internal(0, [1,1,0,0]), quadTree2: Internal(0, [0,0,1,1])
• Output: Represents [[1,1,1,1],[1,1,1,1],[0,0,1,1],[0,0,1,1]]
• OR combines grids, may simplify to quad-tree.
• Input:
• quadTree1: Leaf(1,0), quadTree2: Leaf(1,1)
• Output: Leaf(1,1)
• 0 OR 1 = 1.

Understanding the Problem: Merging Quad-Trees

To solve LeetCode 558: Logical OR of Two Binary Grids Represented as Quad-Trees in Python, we need to merge two quad-trees into one that represents the logical OR of their corresponding binary grids. A quad-tree compresses a grid by dividing it into four quadrants, either as a leaf (uniform value) or an internal node (split into four subtrees). A naive approach might reconstruct the grids and OR them (O(n²)), but with n up to 2⁹ (512), recursive merging leverages the tree structure for efficiency. We’ll explore:

• Best Solution (Recursive Quad-Tree Merging): O(n) time, O(h) space (n = nodes, h = height)—efficient and elegant.
• Alternative Solution (Brute-Force Grid Reconstruction): O(n²) time, O(n²) space—simple but wasteful.

Let’s dive into the recursive solution with a friendly breakdown!

Best Solution: Recursive Quad-Tree Merging

Why Recursive Wins

The recursive quad-tree merging is the best for LeetCode 558 because it computes the OR result in O(n) time (n = total nodes) and O(h) space (h = tree height) by traversing both trees simultaneously, merging nodes based on their structure and values, and reconstructing a simplified quad-tree where possible. It’s like blending two tree-maps layer-by-layer, keeping the structure tidy and efficient!

How It Works

Think of this as a quad-tree blender:

• Step 1: Base Cases:
• Both leaves: OR their values, return new leaf if uniform.
• Step 2: Recursive Merge:
• If one is a leaf:
• If value 1, return it (1 OR anything = 1).
• If value 0, return other tree (0 OR x = x).
• If both internal:
• Recursively merge four child pairs.
• If all resulting children are leaves with same value, simplify to leaf.
• Step 3: Construct Result:
• Build new node with merged children or simplified leaf.
• Why It Works:
• Recursion handles tree structure naturally.
• Simplification reduces complexity where possible.

It’s like a quad-tree fusion master!

Step-by-Step Example

Example: quadTree1 = Leaf(1,1), quadTree2 = Leaf(1,0)

• Step 1: Both leaves.
• Step 2: OR values: 1 OR 0 = 1.
• Step 3: Return Leaf(1,1).
• Result: Leaf(1,1).

Example: quadTree1 = Internal(0, [1,1,0,0]), quadTree2 = Internal(0, [0,0,1,1])

• Grid Representation:
• quadTree1: [[1,1,0,0],[1,1,0,0],[0,0,0,0],[0,0,0,0]].
• quadTree2: [[0,0,0,0],[0,0,0,0],[1,1,1,1],[1,1,1,1]].
• Step 1: Both internal, merge children:
• TL: 1 OR 0 = 1.
• TR: 1 OR 0 = 1.
• BL: 0 OR 1 = 1.
• BR: 0 OR 1 = 1.
• Step 2: All children leaves with value 1, simplify.
• Result: Leaf(1,1).

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

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

class Solution:
    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':
        # Step 1: Both leaves, compute OR
        if quadTree1.isLeaf and quadTree2.isLeaf:
            val = 1 if quadTree1.val == 1 or quadTree2.val == 1 else 0
            return Node(True, val, None, None, None, None)

        # Step 2: One leaf, handle based on value
        if quadTree1.isLeaf:
            return quadTree1 if quadTree1.val == 1 else quadTree2
        if quadTree2.isLeaf:
            return quadTree2 if quadTree2.val == 1 else quadTree1

        # Step 3: Both internal, recursively merge children
        tl = self.intersect(quadTree1.topLeft, quadTree2.topLeft)
        tr = self.intersect(quadTree1.topRight, quadTree2.topRight)
        bl = self.intersect(quadTree1.bottomLeft, quadTree2.bottomLeft)
        br = self.intersect(quadTree1.bottomRight, quadTree2.bottomRight)

        # Step 4: Simplify if all leaves with same value
        if (tl.isLeaf and tr.isLeaf and bl.isLeaf and br.isLeaf and
            tl.val == tr.val == bl.val == br.val):
            return Node(True, tl.val, None, None, None, None)

        # Step 5: Return internal node with merged children
        return Node(False, 0, tl, tr, bl, br)

• Lines 13-15: Both leaves, OR values, return new leaf.
• Lines 18-21: One leaf, return 1-leaf or other tree.
• Lines 24-27: Recursively merge four child pairs.
• Lines 30-32: Simplify to leaf if all children uniform.
• Line 35: Return internal node with children.
• Time Complexity: O(n)—n nodes visited once.
• Space Complexity: O(h)—recursion stack (h ≤ log n).

It’s like a quad-tree merger!

Alternative Solution: Brute-Force Grid Reconstruction

Why an Alternative Approach?

The brute-force grid reconstruction converts both quad-trees to full grids, performs OR, and rebuilds a quad-tree, running in O(n²) time and O(n²) space (n = grid side length). It’s simple but wasteful, making it a good baseline for understanding or small grids.

How It Works

Picture this as a grid-rebuilding mixer:

• Step 1: Reconstruct grids from quad-trees.
• Step 2: OR corresponding cells.
• Step 3: Build new quad-tree from result.
• Step 4: Return quad-tree.

It’s like a grid-blending rebuilder!

Step-by-Step Example

Example: quadTree1 = Leaf(1,1), quadTree2 = Leaf(1,0)

• Step 1: Grids: [[1]], [[0]].
• Step 2: OR: [[1]].
• Step 3: Quad-tree: Leaf(1,1).
• Result: Leaf(1,1).

Code for Brute-Force Approach

class Solution:
    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':
        def to_grid(node, size, x=0, y=0):
            grid = [[0] * size for _ in range(size)]
            if node.isLeaf:
                for i in range(x, x + size):
                    for j in range(y, y + size):
                        grid[i][j] = node.val
            else:
                half = size // 2
                to_grid(node.topLeft, half, x, y)
                to_grid(node.topRight, half, x, y + half)
                to_grid(node.bottomLeft, half, x + half, y)
                to_grid(node.bottomRight, half, x + half, y + half)
            return grid

        def build_quad(grid, size, x=0, y=0):
            if size == 1:
                return Node(True, grid[x][y], None, None, None, None)
            half = size // 2
            tl = build_quad(grid, half, x, y)
            tr = build_quad(grid, half, x, y + half)
            bl = build_quad(grid, half, x + half, y)
            br = build_quad(grid, half, x + half, y + half)
            if tl.isLeaf and tr.isLeaf and bl.isLeaf and br.isLeaf and tl.val == tr.val == bl.val == br.val:
                return Node(True, tl.val, None, None, None, None)
            return Node(False, 0, tl, tr, bl, br)

        # Assume size from tree depth (e.g., 2^k)
        size = 1
        while size * size < sum(1 for _ in range(10)):  # Simplified size calc
            size *= 2

        grid1 = to_grid(quadTree1, size)
        grid2 = to_grid(quadTree2, size)
        result_grid = [[grid1[i][j] | grid2[i][j] for j in range(size)] for i in range(size)]
        return build_quad(result_grid, size)

• Lines 5-15: Convert quad-tree to grid.
• Lines 17-27: Build quad-tree from grid.
• Lines 31-36: Reconstruct grids, OR, rebuild.
• Time Complexity: O(n²)—grid operations.
• Space Complexity: O(n²)—grid storage.

It’s a grid-rebuilding mixer!

Comparing the Two Solutions

• Recursive (Best):
• Pros: O(n), O(h), efficient.
• Cons: Recursive logic.
• Brute-Force (Alternative):
• Pros: O(n²), O(n²), simple.
• Cons: Wasteful space/time.

Recursive wins for efficiency!

Additional Examples and Edge Cases

• Both 0-leaves: Leaf(1,0).
• Mixed grids: Handled by recursion.
• Single node: OR’d directly.

Recursive handles them all!

Complexity Recap

• Recursive: Time O(n), Space O(h).
• Brute-Force: Time O(n²), Space O(n²).

Recursive’s the efficiency champ!

Key Takeaways

• Recursive: Tree merging—learn at Python Basics!
• Brute-Force: Grid rebuild.
• Quad-Trees: OR is fun.
• Python: Recurse or brute, your pick!

Final Thoughts: Merge Those Grids!

LeetCode 558: Logical OR of Two Binary Grids Represented as Quad-Trees in Python is a clever tree challenge. Recursive quad-tree merging is your fast track, while brute-force offers a clear start. Want more? Try LeetCode 427: Construct Quad Tree or LeetCode 199: Binary Tree Right Side View. Ready to blend? Head to Solve LeetCode 558 on LeetCode and merge those quad-trees today!