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

A clear explanation of merging two quad-trees using recursive logical OR operations.

leetcodetreequad-treerecursion

Problem Restatement

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

Each grid cell contains either:

Value Meaning
0 False
1 True

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

The logical OR rule is:

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

Each quad-tree node contains:

Field Meaning
val Boolean value
isLeaf Whether the node is a leaf
topLeft Top-left child
topRight Top-right child
bottomLeft Bottom-left child
bottomRight Bottom-right child

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.

Input and Output

Item Meaning
Input Two quad-tree roots
Output Root of the OR result quad-tree
Operation Logical OR
Grid sizes Same size

Example function shape:

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

Understanding Quad-Trees

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

Child Region
topLeft Upper-left
topRight Upper-right
bottomLeft Lower-left
bottomRight Lower-right

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:

Child Value
topLeft leaf 1
topRight leaf 1
bottomLeft leaf 1
bottomRight leaf 1

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.

Metric Value Why
Time O(n) Each relevant node pair is processed once
Space O(h) Recursive call stack height

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")
Test Why
1 OR 0 Immediate leaf shortcut
0 OR 0 Uniform false region
0 OR internal Internal subtree should remain unchanged
Recursive internal cases Checks recursive merging logic
Compression cases Ensures identical children collapse into one leaf