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

Problem Restatement

We are given two quad-trees representing two binary grids.

Each grid cell contains either:

We need to compute the logical OR of the two grids and return the result as a quad-tree.

The logical OR rule is:

Each quad-tree node contains:

A leaf node means the entire represented region has one uniform value.

The problem asks us to return a quad-tree representing the OR result. The statement guarantees both input trees represent grids of the same size. (github.com)

Input and Output

Example function shape:

def intersect(quadTree1: 'Node', quadTree2: 'Node') -> 'Node':
    ...

Understanding Quad-Trees

A quad-tree recursively divides a square into four equal regions:

A leaf node represents a completely uniform region.

For example:

isLeaf = True
val = 1

means the entire represented square is filled with 1.

First Thought: Rebuild the Entire Grid

One idea is:

1. Expand both quad-trees into full binary grids.
2. Compute the OR cell by cell.
3. Compress the result back into a quad-tree.

This works logically, but it wastes memory and ignores the compression already provided by quad-trees.

We should operate directly on the trees.

Key Insight

Quad-trees already represent large uniform regions compactly.

Suppose one node is:

isLeaf = True
val = 1

Then the entire region is all 1.

For logical OR:

1 OR anything = 1

So we can immediately return that node without exploring the other tree.

Similarly:

0 OR x = x

So if a leaf node has value 0, the result is exactly the other subtree.

This gives a recursive solution.

Important Cases

Case 1: First Node Is Leaf With Value 1

1 OR x = 1

Return the first node.

Case 2: Second Node Is Leaf With Value 1

x OR 1 = 1

Return the second node.

Case 3: First Node Is Leaf With Value 0

0 OR x = x

Return the second node.

Case 4: Second Node Is Leaf With Value 0

x OR 0 = x

Return the first node.

Case 5: Both Nodes Are Internal

Recursively OR the four children.

Algorithm

For nodes a and b:

1. If a is a leaf:

   1. If a.val == True, return a.
   2. Otherwise return b.

2. If b is a leaf:

   1. If b.val == True, return b.
   2. Otherwise return a.

3. Recursively compute:

   topLeft
   topRight
   bottomLeft
   bottomRight

4. After recursion, check whether all four children are leaves with the same value.

5. If yes, compress them into one leaf node.

6. Otherwise return an internal node containing those four children.

Why Compression Is Needed

Suppose after recursion we get:

These four children together represent one uniform region.

Instead of keeping four separate nodes, we compress them into:

isLeaf = True
val = 1

This keeps the tree minimal.

Correctness

The algorithm follows the exact definition of logical OR.

If one node is a leaf with value 1, then every cell in that represented region is 1. Since:

1 OR x = 1

the entire output region must also be all 1. Returning that leaf is correct.

If one node is a leaf with value 0, then:

0 OR x = x

So the output region is exactly the other subtree. Returning the other subtree is correct.

When both nodes are internal, the represented regions are subdivided into four matching quadrants. The logical OR for the whole region is therefore obtained by computing the OR independently on each corresponding quadrant. The recursive calls correctly compute these four quadrant results.

After recursion, if all four children are leaves with the same value, then the whole region is uniform. Replacing those four leaves with one larger leaf preserves the represented grid exactly while producing a more compact quad-tree.

Therefore, every returned node represents exactly the logical OR of the corresponding regions in the two input trees.

Complexity

Let n be the total number of nodes visited.

Here h is the maximum tree height.

In the worst case, all nodes may need to be explored.

Implementation

class Solution:
    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':
        if quadTree1.isLeaf:
            if quadTree1.val:
                return quadTree1
            return quadTree2

        if quadTree2.isLeaf:
            if quadTree2.val:
                return quadTree2
            return 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)

        children = [topLeft, topRight, bottomLeft, bottomRight]

        if (
            all(child.isLeaf for child in children)
            and topLeft.val == topRight.val == bottomLeft.val == bottomRight.val
        ):
            return Node(topLeft.val, True)

        return Node(
            False,
            False,
            topLeft,
            topRight,
            bottomLeft,
            bottomRight,
        )

Code Explanation

We first handle leaf shortcuts.

If the first tree is a leaf:

if quadTree1.isLeaf:

and its value is True, then the OR result must also be True everywhere in that region:

if quadTree1.val:
    return quadTree1

Otherwise, the first region is all 0, so the result is just the second tree:

return quadTree2

We do the symmetric logic for the second tree.

If both nodes are internal, we recursively combine corresponding children:

topLeft = self.intersect(...)

After recursion, we check whether all children became identical leaf nodes:

all(child.isLeaf for child in children)

and:

topLeft.val == topRight.val == bottomLeft.val == bottomRight.val

If so, we compress them into one leaf node.

Otherwise, we return an internal node containing the four children.

Testing

def run_tests():
    s = Solution()

    # Leaf true OR leaf false -> true
    a = Node(True, True)
    b = Node(False, True)

    result = s.intersect(a, b)
    assert result.isLeaf is True
    assert result.val is True

    # Leaf false OR leaf false -> false
    a = Node(False, True)
    b = Node(False, True)

    result = s.intersect(a, b)
    assert result.isLeaf is True
    assert result.val is False

    # Leaf false OR internal -> internal
    internal = Node(
        False,
        False,
        Node(True, True),
        Node(False, True),
        Node(False, True),
        Node(True, True),
    )

    result = s.intersect(Node(False, True), internal)
    assert result.isLeaf is False

    print("all tests passed")