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

LeetCode Problem 558

Difficulty: 🟡 Medium
Topics: Divide and Conquer, Tree

Solution

Problem Understanding

This problem gives us two Quad-Trees, where each tree represents a binary matrix containing only 0s and 1s. Our goal is to compute the logical bitwise OR of the two matrices and return the result as another Quad-Tree.

A Quad-Tree is a recursive spatial data structure. Every node represents a square region of the matrix.

If the entire region contains the same value, either all 0s or all 1s, the region is compressed into a leaf node:

• isLeaf = True
• val = True if the region is all 1s
• val = False if the region is all 0s

If the region contains mixed values, the node becomes an internal node:

• isLeaf = False

• the region is split into four equal quadrants:

• top-left

• top-right

• bottom-left

• bottom-right

The important observation is that the trees already store compressed representations of the matrices. Constructing the full matrices would destroy this compression advantage and waste both time and memory.

The logical OR operation behaves as follows:

A	B	A OR B
0	0	0
0	1	1
1	0	1
1	1	1

This means that if one region is entirely 1, the OR result for that region must also be entirely 1, regardless of the other tree.

The constraints tell us that:

• The matrix size is n = 2^x
• 0 <= x <= 9
• Maximum matrix size is 512 x 512

A full matrix representation could contain over 260,000 cells, but Quad-Trees can compress large uniform regions efficiently. The intended solution must operate directly on the trees rather than expanding them into matrices.

Several edge cases are important:

• Both trees may already be leaf nodes.
• One tree may be a leaf while the other is deeply subdivided.
• A leaf with value 1 immediately dominates the OR result.
• After recursively combining children, the result may become compressible again into a single leaf node.
• Internal nodes may have arbitrary val values because the problem explicitly says internal node values do not matter.

Approaches

Brute Force Approach

The brute force solution would first reconstruct both binary matrices from the Quad-Trees. After that, we would compute the OR operation cell by cell and then rebuild a new Quad-Tree from the resulting matrix.

This approach works because it directly follows the problem definition:

1. Decode both trees into full matrices.
2. Compute matrix OR.
3. Rebuild a compressed Quad-Tree.

Although conceptually simple, this approach is inefficient because it loses the compression benefits of Quad-Trees. Even if a tree represents a huge uniform region with a single node, the brute force method expands it into many individual cells.

For the maximum size 512 x 512, reconstructing matrices requires processing all 262,144 cells.

Optimal Recursive Quad-Tree Merge

The key insight is that we can perform the OR operation directly on the Quad-Trees without reconstructing matrices.

Quad-Trees are recursive structures, and the OR operation is naturally recursive across regions.

The most important optimization comes from OR logic:

• 1 OR anything = 1
• 0 OR x = x

This creates two powerful pruning rules:

• If either node is a leaf with value 1, the result for the entire region is immediately 1.
• If one node is a leaf with value 0, the result is exactly the other subtree.

When neither shortcut applies, we recursively merge corresponding quadrants.

After recursively merging children, we check whether all four children became identical leaf nodes. If so, we compress them into a single leaf node to preserve Quad-Tree compactness.

This solution avoids unnecessary expansion and works directly on the compressed representation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n²)	Expands entire matrices before rebuilding tree
Optimal	O(m)	O(h)	Processes only Quad-Tree nodes, where m is total nodes

Here:

• m is the number of nodes visited across both trees
• h is the recursion depth

Algorithm Walkthrough

1. Start with the two current Quad-Tree nodes.

Each recursive call represents computing the OR result for the same spatial region in both trees. 2. Check whether the first node is a leaf.

If it is a leaf with value True, then the OR result for the entire region must also be True. We can immediately return this node because:

1 OR x = 1

If it is a leaf with value False, then:

0 OR x = x

So we simply return the second node. 3. Perform the same check for the second node.

The same logical simplifications apply symmetrically. 4. If neither node is a leaf, recursively merge all four quadrants.

We recursively compute:

• top-left with top-left
• top-right with top-right
• bottom-left with bottom-left
• bottom-right with bottom-right

5. After recursion, check whether all four children are leaf nodes with the same value.

If they are, the region has become uniform again after merging.

In that case, compress the four children into a single leaf node. 6. Otherwise, create an internal node containing the four merged children.

The val field for internal nodes can be anything because the problem explicitly allows arbitrary values when isLeaf = False.

Why it works

The algorithm works because every recursive call processes exactly the same spatial region in both trees. The OR operation is independently valid for each quadrant, so recursively combining matching quadrants produces the correct matrix result.

The pruning rules are mathematically guaranteed by OR logic:

• 1 OR x = 1
• 0 OR x = x

The final compression step preserves correctness because four identical leaf children represent a uniform region, which is exactly the definition of a compressible Quad-Tree region.

Python Solution

"""
# 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
"""

from typing import Optional

class Solution:
    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':

        # If quadTree1 is a leaf, OR logic gives an immediate answer
        if quadTree1.isLeaf:
            if quadTree1.val:
                return quadTree1
            return quadTree2

        # If quadTree2 is a leaf, OR logic gives an immediate answer
        if quadTree2.isLeaf:
            if quadTree2.val:
                return quadTree2
            return quadTree1

        # Recursively merge all four quadrants
        top_left = self.intersect(
            quadTree1.topLeft,
            quadTree2.topLeft
        )

        top_right = self.intersect(
            quadTree1.topRight,
            quadTree2.topRight
        )

        bottom_left = self.intersect(
            quadTree1.bottomLeft,
            quadTree2.bottomLeft
        )

        bottom_right = self.intersect(
            quadTree1.bottomRight,
            quadTree2.bottomRight
        )

        children = [
            top_left,
            top_right,
            bottom_left,
            bottom_right
        ]

        # Compress if all children are identical leaves
        all_leaf = all(child.isLeaf for child in children)

        same_value = (
            top_left.val ==
            top_right.val ==
            bottom_left.val ==
            bottom_right.val
        )

        if all_leaf and same_value:
            return Node(
                top_left.val,
                True,
                None,
                None,
                None,
                None
            )

        # Otherwise create an internal node
        return Node(
            False,
            False,
            top_left,
            top_right,
            bottom_left,
            bottom_right
        )

The implementation directly follows the recursive structure of the Quad-Tree.

The first two conditional blocks implement the OR pruning logic. These are the most important optimizations because they allow entire subtrees to be skipped.

If neither node is a leaf, the function recursively processes corresponding quadrants. Since both nodes represent the same spatial region, each pair of child nodes also corresponds to the same subregion.

After recursion, the implementation checks whether the resulting children are all leaf nodes with identical values. If so, the subtree is compressed into a single leaf node. This keeps the result tree compact and preserves proper Quad-Tree structure.

Finally, if compression is not possible, an internal node is returned with the merged children attached.

Go Solution

/**
 * Definition for a QuadTree node.
 * type Node struct {
 *     Val bool
 *     IsLeaf bool
 *     TopLeft *Node
 *     TopRight *Node
 *     BottomLeft *Node
 *     BottomRight *Node
 * }
 */

func intersect(quadTree1 *Node, quadTree2 *Node) *Node {

    // If quadTree1 is a leaf, OR logic gives an immediate answer
    if quadTree1.IsLeaf {
        if quadTree1.Val {
            return quadTree1
        }
        return quadTree2
    }

    // If quadTree2 is a leaf, OR logic gives an immediate answer
    if quadTree2.IsLeaf {
        if quadTree2.Val {
            return quadTree2
        }
        return quadTree1
    }

    // Recursively merge quadrants
    topLeft := intersect(
        quadTree1.TopLeft,
        quadTree2.TopLeft,
    )

    topRight := intersect(
        quadTree1.TopRight,
        quadTree2.TopRight,
    )

    bottomLeft := intersect(
        quadTree1.BottomLeft,
        quadTree2.BottomLeft,
    )

    bottomRight := intersect(
        quadTree1.BottomRight,
        quadTree2.BottomRight,
    )

    // Compress if all children are identical leaves
    if topLeft.IsLeaf &&
        topRight.IsLeaf &&
        bottomLeft.IsLeaf &&
        bottomRight.IsLeaf &&
        topLeft.Val == topRight.Val &&
        topLeft.Val == bottomLeft.Val &&
        topLeft.Val == bottomRight.Val {

        return &Node{
            Val:      topLeft.Val,
            IsLeaf:   true,
            TopLeft:  nil,
            TopRight: nil,
            BottomLeft: nil,
            BottomRight: nil,
        }
    }

    // Otherwise return an internal node
    return &Node{
        Val:         false,
        IsLeaf:      false,
        TopLeft:     topLeft,
        TopRight:    topRight,
        BottomLeft:  bottomLeft,
        BottomRight: bottomRight,
    }
}

The Go implementation is structurally identical to the Python version. The main difference is explicit pointer handling with *Node.

Go uses nil instead of None, and all node allocations are done with &Node{}. Since recursion depth is limited by the matrix size, stack overflow is not a practical concern here.

Worked Examples

Example 1

Input:

quadTree1 = [[0,1],[1,1],[1,1],[1,0],[1,0]]
quadTree2 = [[0,1],[1,1],[0,1],[1,1],[1,0],...]

Suppose we recursively process corresponding quadrants.

Step	quadTree1 Region	quadTree2 Region	Result
1	Internal node	Internal node	Recurse
2	Top-left = leaf(1)	Top-left = leaf(1)	leaf(1)
3	Top-right = leaf(1)	Top-right = internal	leaf(1), shortcut
4	Bottom-left = leaf(0)	Bottom-left = leaf(0)	leaf(0)
5	Bottom-right = leaf(0)	Bottom-right = leaf(0)	leaf(0)

At the end, the four merged children are:

1, 1, 0, 0

Since they are not identical, compression is impossible.

The algorithm returns an internal node containing those four children.

Example 2

Input:

quadTree1 = [[1,0]]
quadTree2 = [[1,0]]

Both trees are leaf nodes with value 0.

Execution:

Step	Node 1	Node 2	Action
1	leaf(0)	leaf(0)	return second tree

Since:

0 OR 0 = 0

The result is simply a leaf node representing 0.

Output:

[[1,0]]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m)	Each Quad-Tree node is processed at most once
Space	O(h)	Recursive call stack depth equals tree height

Here:

• m is the total number of nodes visited across both trees
• h is the maximum depth of the Quad-Tree

The algorithm is efficient because it never expands compressed regions into full matrices. Large uniform regions may terminate recursion immediately through the OR pruning rules.

The recursion depth is bounded by log₂(n), which is at most 9 for the given constraints.

Test Cases

# Helper Node class for testing
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

solution = Solution()

# Test 1: both zero leaves
t1 = Node(False, True)
t2 = Node(False, True)

result = solution.intersect(t1, t2)

assert result.isLeaf is True
assert result.val is False  # 0 OR 0 = 0

# Test 2: one leaf is true
t1 = Node(True, True)
t2 = Node(False, True)

result = solution.intersect(t1, t2)

assert result.isLeaf is True
assert result.val is True  # 1 OR 0 = 1

# Test 3: false leaf with internal node
internal = Node(
    False,
    False,
    Node(True, True),
    Node(False, True),
    Node(False, True),
    Node(True, True)
)

t1 = Node(False, True)

result = solution.intersect(t1, internal)

assert result == internal  # 0 OR x = x

# Test 4: compression after merge
a = Node(
    False,
    False,
    Node(True, True),
    Node(True, True),
    Node(True, True),
    Node(True, True)
)

b = Node(False, True)

result = solution.intersect(a, b)

assert result.isLeaf is True
assert result.val is True  # compresses into one leaf

# Test 5: mixed children remain internal
a = Node(
    False,
    False,
    Node(True, True),
    Node(False, True),
    Node(False, True),
    Node(True, True)
)

b = Node(False, True)

result = solution.intersect(a, b)

assert result.isLeaf is False  # cannot compress

# Test 6: deep recursive merge
a = Node(
    False,
    False,
    Node(False, True),
    Node(False, True),
    Node(False, True),
    Node(False, True)
)

b = Node(
    False,
    False,
    Node(False, True),
    Node(True, True),
    Node(False, True),
    Node(False, True)
)

result = solution.intersect(a, b)

assert result.isLeaf is False
assert result.topRight.val is True  # only one quadrant becomes true

Test	Why
Both zero leaves	Verifies basic OR behavior
One true leaf	Tests OR domination shortcut
False leaf with internal node	Ensures subtree reuse works correctly
Compression after merge	Verifies subtree compression logic
Mixed children remain internal	Ensures non-uniform regions are preserved
Deep recursive merge	Tests recursive quadrant processing

Edge Cases

One subtree is entirely 1

This is the most important optimization case. If a node is a leaf with value True, the OR result for the entire region must also be True.

A buggy implementation might continue recursing unnecessarily into the other tree, wasting time and potentially producing incorrect structure.

The implementation avoids this by immediately returning the True leaf node.

One subtree is entirely 0

A leaf node representing all zeros contributes nothing to the OR operation:

0 OR x = x

A naive implementation might still recursively traverse both trees. The optimized solution simply returns the other subtree directly.

This both improves efficiency and preserves existing compression.

Four merged children become identical

After recursive merging, four separate quadrants may all become identical leaf nodes.

For example:

topLeft     = leaf(1)
topRight    = leaf(1)
bottomLeft  = leaf(1)
bottomRight = leaf(1)

A buggy implementation might leave these as separate children, creating an unnecessarily large tree.

The implementation explicitly checks for this condition and compresses the node into a single leaf, preserving the canonical compact Quad-Tree representation.