#558

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Logical OR of Two Binary Grids Represented as Quad-Trees

Compute the logical OR of two binary matrices represented as Quad-Trees using recursive tree traversal and state propagation.

divide and conquer tree

Problem Statement

You are given two n * n binary matrices represented as Quad-Trees, where each leaf node holds either 0 or 1. Your task is to compute the logical bitwise OR of these matrices and return the result as a Quad-Tree.

Each Quad-Tree node contains a boolean value and pointers to four children representing top-left, top-right, bottom-left, and bottom-right quadrants. If a node is a leaf, its value applies to the entire region; otherwise, its children recursively define subregions. Merge the two trees following logical OR rules to construct the resulting Quad-Tree.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

class Node { public boolean val; public boolean isLeaf; public Node topLeft; public Node topRight; public Node bottomLeft; public Node bottomRight; }

Example 2

Input: quadTree1 = [[0,1],[1,1],[1,1],[1,0],[1,0]] , quadTree2 = [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]

Output: [[0,0],[1,1],[1,1],[1,1],[1,0]]

quadTree1 and quadTree2 are shown above. You can see the binary matrix which is represented by each Quad-Tree. If we apply logical bitwise OR on the two binary matrices we get the binary matrix below which is represented by the result Quad-Tree. Notice that the binary matrices shown are only for illustration, you don't have to construct the binary matrix to get the result tree.

Example 3

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

Output: [[1,0]]

Each tree represents a binary matrix of size 1 1. Each matrix contains only zero. The resulting matrix is of size 1 1 with also zero.

Constraints

quadTree1 and quadTree2 are both valid Quad-Trees each representing a n * n grid.
n == 2x where 0 <= x <= 9.

Solution Approach

Recursive Leaf Handling

If either node is a leaf with value true, the resulting region is entirely true. If both nodes are leaves, compute OR directly. This ensures base cases are handled without unnecessary recursion.

Divide and Conquer Merge

For internal nodes, recursively merge corresponding top-left, top-right, bottom-left, and bottom-right children. After recursion, if all four children of the result are leaves with identical values, compress them into a single leaf node.

State Propagation Optimization

Track leaf values and avoid expanding nodes representing uniform regions. This reduces tree size and memory usage, aligning with the Quad-Tree pattern of representing large uniform blocks efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) in the worst case when every cell is different, because each node may need to be visited once. Space complexity is also O(n^2) due to recursive call stack and potential creation of new Quad-Tree nodes for the result.

What Interviewers Usually Probe

Ask clarifying questions about leaf node representation and uniform region compression.
Look for correct recursive traversal and proper handling of OR at leaf nodes.
Expect discussion of time and space trade-offs between expanding every node versus compressing identical leaves.

Common Pitfalls or Variants

Common pitfalls

Forgetting to compress four identical child leaves into one parent leaf after recursion.
Incorrectly handling cases where one node is a leaf and the other is not, leading to unnecessary recursion.
Mixing up quadrant order, which produces an incorrect merged Quad-Tree structure.

Follow-up variants

Logical AND of two Quad-Tree binary grids instead of OR.
Supporting non-square or non-power-of-two matrices with Quad-Tree adaptation.
Counting the number of true cells in the resulting Quad-Tree without building the tree explicitly.

FAQ

What is the main approach to solve Logical OR of Two Binary Grids Represented as Quad-Trees?

Traverse both Quad-Trees recursively, apply logical OR at leaves, merge internal nodes, and compress identical child leaves into a single node.

How do I handle a leaf node ORed with an internal node?

If the leaf node is true, the result for that region is true; if false, recursively merge the internal node's children with the leaf.

Can we avoid constructing the full binary matrix?

Yes, operating directly on Quad-Trees lets you compute the result efficiently without converting back to a full n * n matrix.

What is the worst-case time complexity for merging two Quad-Trees?

O(n^2), occurring when every cell differs and recursion must visit every node in both trees.

Why do we compress four identical child leaves into one parent leaf?

To maintain Quad-Tree efficiency and reduce memory usage, ensuring uniform regions are represented by a single leaf node.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

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


class Solution:
    def intersect(self, quadTree1: "Node", quadTree2: "Node") -> "Node":
        def dfs(t1, t2):
            if t1.isLeaf and t2.isLeaf:
                return Node(t1.val or t2.val, True)
            if t1.isLeaf:
                return t1 if t1.val else t2
            if t2.isLeaf:
                return t2 if t2.val else t1
            res = Node()
            res.topLeft = dfs(t1.topLeft, t2.topLeft)
            res.topRight = dfs(t1.topRight, t2.topRight)
            res.bottomLeft = dfs(t1.bottomLeft, t2.bottomLeft)
            res.bottomRight = dfs(t1.bottomRight, t2.bottomRight)
            isLeaf = (
                res.topLeft.isLeaf
                and res.topRight.isLeaf
                and res.bottomLeft.isLeaf
                and res.bottomRight.isLeaf
            )
            sameVal = (
                res.topLeft.val
                == res.topRight.val
                == res.bottomLeft.val
                == res.bottomRight.val
            )
            if isLeaf and sameVal:
                res = res.topLeft
            return res

        return dfs(quadTree1, quadTree2)

Continue Practicing

#654 maximum binary tree #427 construct quad tree #889 construct binary tree from preorder and postorder traversal