558. Logical OR of Two Binary Grids Quad-Trees

Q: Is Logical OR of Two Binary Grids Represented as Quad-Trees easy or hard?

The problem is rated Medium because the OR logic itself is simple but the quad-tree merging and compression rules require careful implementation. Candidates must correctly handle leaf cases, recursive quadrant merging, and post-merge compression. Understanding tree recursion makes the solution straightforward.

Q: Logical OR of Two Binary Grids Represented as Quad-Trees Python/Java solution

Python and Java implementations typically use a recursive helper function that accepts two nodes and returns the merged node. The function handles base cases for leaf nodes, recursively merges child quadrants, and compresses identical children into a single leaf node. Both implementations achieve O(n) time complexity with clean tree recursion.

Q: How to solve Logical OR of Two Binary Grids Represented as Quad-Trees in O(n)?

Traverse both quad-trees simultaneously and merge corresponding nodes. If either node is a leaf with value 1, return a leaf 1 for that region because OR(1, x) is always 1. Otherwise recursively merge the four child quadrants and compress them if all children become identical leaf nodes. Each node pair is processed once, giving O(n) time complexity.

Q: What is the best approach for Logical OR of Two Binary Grids Represented as Quad-Trees?

The recursive quad-tree merge approach is the most practical solution. It compares corresponding nodes from both trees and applies the logical OR rule while recursively merging child quadrants. If either node is a leaf with value 1, the result becomes a leaf 1 immediately. This method runs in O(n) time and uses O(h) recursion stack space, where h is the tree height.

Q: Is Logical OR of Two Binary Grids Represented as Quad-Trees asked at Google/Amazon/Meta?

Quad-tree and divide-and-conquer problems appear in interviews at companies like Google, Amazon, and Meta when discussing spatial data structures or hierarchical grids. Variants of this problem test recursive tree merging and compression logic. The problem focuses on reasoning about tree structures rather than complex algorithms.

Q: What data structure is used in Logical OR of Two Binary Grids Represented as Quad-Trees?

The primary data structure is a quad-tree, a hierarchical tree where each internal node has exactly four children representing quadrants of a grid. The algorithm also uses recursion or an explicit stack for traversal. Quad-trees are commonly used in spatial indexing, image compression, and grid partitioning problems.

Q: What is the time complexity of Logical OR of Two Binary Grids Represented as Quad-Trees?

The optimal time complexity is O(n), where n is the total number of nodes visited across both quad-trees. Each pair of nodes is processed at most once while merging the four quadrants. Space complexity is O(h) for the recursive stack or O(n) for the iterative stack-based traversal.

The problem

A Binary Matrix is a matrix in which all the elements are either 0 or 1.

Given quadTree1 and quadTree2. quadTree1 represents a n * n binary matrix and quadTree2 represents another n * n binary matrix.

Return a Quad-Tree representing the n * n binary matrix which is the result of logical bitwise OR of the two binary matrixes represented by quadTree1 and quadTree2.

Notice that you can assign the value of a node to True or False when isLeaf is False, and both are accepted in the answer.

A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:

val: True if the node represents a grid of 1's or False if the node represents a grid of 0's.
isLeaf: True if the node is leaf node on the tree or False if the node has the four children.

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

We can construct a Quad-Tree from a two-dimensional area using the following steps:

If the current grid has the same value (i.e all 1's or all 0's) set isLeaf True and set val to the value of the grid and set the four children to Null and stop.
If the current grid has different values, set isLeaf to False and set val to any value and divide the current grid into four sub-grids as shown in the photo.
Recurse for each of the children with the proper sub-grid.

If you want to know more about the Quad-Tree, you can refer to the wiki.

Quad-Tree format:

The input/output represents the serialized format of a Quad-Tree using level order traversal, where null signifies a path terminator where no node exists below.

It is very similar to the serialization of the binary tree. The only difference is that the node is represented as a list [isLeaf, val].

If the value of isLeaf or val is True we represent it as 1 in the list [isLeaf, val] and if the value of isLeaf or val is False we represent it as 0.

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],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
Output: [[0,0],[1,1],[1,1],[1,1],[1,0]]
Explanation: 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 2:

Input: quadTree1 = [[1,0]], quadTree2 = [[1,0]]
Output: [[1,0]]
Explanation: 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 == 2^x where 0 <= x <= 9.

Approach overview

Problem Overview: Two binary grids are compressed using quad-trees. Each node represents a region that is either entirely 0, entirely 1, or subdivided into four children. Your task is to compute the logical OR of the two grids and return the resulting quad-tree structure.

Approach 1: Recursive Merge of Quad-Trees (O(n) time, O(h) space)

This approach applies divide and conquer. You recursively merge corresponding nodes from both trees. If either node is a leaf with value 1, the result is immediately a leaf 1 because the OR operation dominates the region. If both nodes are leaves with value 0, the result is a leaf 0. Otherwise recursively merge the four quadrants: topLeft, topRight, bottomLeft, and bottomRight. After recursion, check if all four children become identical leaf nodes; if so, compress them into a single leaf node. This keeps the resulting tree minimal while maintaining correctness.

Approach 2: Iterative Post-Order Traversal Using Stack (O(n) time, O(n) space)

This version avoids recursion by simulating the traversal with an explicit stack. Each stack entry holds a pair of nodes from the two input trees and tracks whether their children have been processed. The algorithm pushes child pairs first (post-order style), computes their merged results, and then combines them into the parent node. Just like the recursive method, if either node is a leaf with value 1, you short‑circuit and return a leaf 1. If all four merged children are leaf nodes with the same value, compress them into a single leaf node to maintain the quad-tree property. This approach is useful when recursion depth could be large or when you want tighter control over traversal state.

Recommended for interviews: The recursive merge is the expected solution. It directly mirrors the quad-tree structure and clearly demonstrates understanding of recursion and divide‑and‑conquer patterns. The iterative stack solution shows deeper mastery of traversal mechanics and can help in environments where recursion depth is constrained.

Approach 1: Recursive Merge of Quad-Trees

This approach involves recursively merging the quad-trees using a depth-first traversal. When encountering a leaf node in one tree, we can determine the result for that section of the grid based on the leaf's value and the corresponding part in the other tree. If both nodes are not leaf nodes, you recursively merge all four children.

Python

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

def mergeQuadTrees(tree1: 'Node', tree2: 'Node') -> 'Node':
    if tree1.isLeaf:
        return tree1 if tree1.val else tree2
    if tree2.isLeaf:
        return tree2 if tree2.val else tree1

    topLeft = mergeQuadTrees(tree1.topLeft, tree2.topLeft)
    topRight = mergeQuadTrees(tree1.topRight, tree2.topRight)
    bottomLeft = mergeQuadTrees(tree1.bottomLeft, tree2.bottomLeft)
    bottomRight = mergeQuadTrees(tree1.bottomRight, tree2.bottomRight)

    if (topLeft.isLeaf and topRight.isLeaf and bottomLeft.isLeaf and bottomRight.isLeaf and
        topLeft.val == topRight.val == bottomLeft.val == bottomRight.val):
        return Node(topLeft.val, True)
    return Node(False, False, topLeft, topRight, bottomLeft, bottomRight)

Java

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

    public Node(boolean _val, boolean _isLeaf) {
        val = _val;
        isLeaf = _isLeaf;
    }

    public Node(boolean _val, boolean _isLeaf, Node _topLeft, Node _topRight, Node _bottomLeft, Node _bottomRight) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
}

class Solution {
    public Node mergeQuadTrees(Node tree1, Node tree2) {
        if (tree1.isLeaf) return tree1.val ? tree1 : tree2;
        if (tree2.isLeaf) return tree2.val ? tree2 : tree1;

        Node topLeft = mergeQuadTrees(tree1.topLeft, tree2.topLeft);
        Node topRight = mergeQuadTrees(tree1.topRight, tree2.topRight);
        Node bottomLeft = mergeQuadTrees(tree1.bottomLeft, tree2.bottomLeft);
        Node bottomRight = mergeQuadTrees(tree1.bottomRight, tree2.bottomRight);

        if (topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf &&
            topLeft.val == topRight.val && topRight.val == bottomLeft.val && bottomLeft.val == bottomRight.val) {
            return new Node(topLeft.val, true);
        }

        return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
    }
}

This function recursively merges two quad-trees. If one of them is a leaf, it checks whether to return the leaf node or recurse further. When not leaves, it recurses into all children nodes and merges them.

Complexity

Time Complexity: O(n^2), where n is the size of the matrix.
Space Complexity: O(log(n)), due to the recursion stack.

Try this approach in the editor

Approach 2: Iterative Post-Order Traversal Using Stack

This solution is designed with an iterative method that employs a post-order traversal of the trees using a stack. This can help avoid recursion depth issues in Python or other environments that could encounter recursion limits.

JavaScript

class Node {
    constructor(val, isLeaf, topLeft=null, topRight=null, bottomLeft=null, bottomRight=null) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
}

function mergeQuadTrees(quadTree1, quadTree2) {
    if (quadTree1.isLeaf) return quadTree1.val ? quadTree1 : quadTree2;
    if (quadTree2.isLeaf) return quadTree2.val ? quadTree2 : quadTree1;

    const topLeft = mergeQuadTrees(quadTree1.topLeft, quadTree2.topLeft);
    const topRight = mergeQuadTrees(quadTree1.topRight, quadTree2.topRight);
    const bottomLeft = mergeQuadTrees(quadTree1.bottomLeft, quadTree2.bottomLeft);
    const bottomRight = mergeQuadTrees(quadTree1.bottomRight, quadTree2.bottomRight);

    if (topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf &&
        topLeft.val === topRight.val && topRight.val === bottomLeft.val && bottomLeft.val === bottomRight.val) {
        return new Node(topLeft.val, true);
    }

    return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
}

public class Node {
    public bool val;
    public bool isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;
    public Node(bool _val, bool _isLeaf) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = topRight = bottomLeft = bottomRight = null;
    }
}

public class Solution {
    public Node MergeQuadTrees(Node quadTree1, Node quadTree2) {
        if (quadTree1.isLeaf) return quadTree1.val ? quadTree1 : quadTree2;
        if (quadTree2.isLeaf) return quadTree2.val ? quadTree2 : quadTree1;

        var topLeft = MergeQuadTrees(quadTree1.topLeft, quadTree2.topLeft);
        var topRight = MergeQuadTrees(quadTree1.topRight, quadTree2.topRight);
        var bottomLeft = MergeQuadTrees(quadTree1.bottomLeft, quadTree2.bottomLeft);
        var bottomRight = MergeQuadTrees(quadTree1.bottomRight, quadTree2.bottomRight);

        if (topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf &&
            topLeft.val == topRight.val && topRight.val == bottomLeft.val && bottomLeft.val == bottomRight.val) {
            return new Node(topLeft.val, true);
        }

        return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
    }
}

This JavaScript version mirrors the recursive logic seen in other languages, using ES6 class syntax to define nodes and merge them through conditional checks and recursion.

Complexity

Time Complexity: O(n^2), where n is the size of the matrix.
Space Complexity: Dependent on stack size but efficient in iterative applications.

Try this approach in the editor

Approach 3: Default Approach

C++

/*
// Definition for a QuadTree node.
class Node {
public:
    bool val;
    bool isLeaf;
    Node* topLeft;
    Node* topRight;
    Node* bottomLeft;
    Node* bottomRight;

    Node() {
        val = false;
        isLeaf = false;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }

    Node(bool _val, bool _isLeaf) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }

    Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
};
*/

class Solution {
public:
    Node* intersect(Node* quadTree1, Node* quadTree2) {
        return dfs(quadTree1, quadTree2);
    }

    Node* dfs(Node* t1, Node* t2) {
        if (t1->isLeaf && t2->isLeaf) return new Node(t1->val || t2->val, true);
        if (t1->isLeaf) return t1->val ? t1 : t2;
        if (t2->isLeaf) return t2->val ? t2 : t1;
        Node* res = new 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);
        bool isLeaf = res->topLeft->isLeaf && res->topRight->isLeaf && res->bottomLeft->isLeaf && res->bottomRight->isLeaf;
        bool sameVal = res->topLeft->val == res->topRight->val && res->topRight->val == res->bottomLeft->val && res->bottomLeft->val == res->bottomRight->val;
        if (isLeaf && sameVal) res = res->topLeft;
        return res;
    }
};

/**
 * 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 {
	var dfs func(*Node, *Node) *Node
	dfs = func(t1, t2 *Node) *Node {
		if t1.IsLeaf && t2.IsLeaf {
			return &Node{Val: t1.Val || t2.Val, IsLeaf: true}
		}
		if t1.IsLeaf {
			if t1.Val {
				return t1
			}
			return t2
		}
		if t2.IsLeaf {
			if t2.Val {
				return t2
			}
			return 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 && res.TopRight.IsLeaf && res.BottomLeft.IsLeaf && res.BottomRight.IsLeaf
		sameVal := res.TopLeft.Val == res.TopRight.Val && res.TopRight.Val == res.BottomLeft.Val && res.BottomLeft.Val == res.BottomRight.Val
		if isLeaf && sameVal {
			res = res.TopLeft
		}
		return res
	}

	return dfs(quadTree1, quadTree2)
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Recursive Merge of Quad-Trees	Time Complexity: O(n^2), where n is the size of the matrix. Space Complexity: O(log(n)), due to the recursion stack.
Iterative Post-Order Traversal Using Stack	Time Complexity: O(n^2), where n is the size of the matrix. Space Complexity: Dependent on stack size but efficient in iterative applications.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Recursive Merge of Quad-Trees	O(n)	O(h)	General case; simplest and most interview-friendly solution
Iterative Post-Order Traversal Using Stack	O(n)	O(n)	When avoiding recursion or managing deep quad-tree structures

Frequently asked questions

Is Logical OR of Two Binary Grids Represented as Quad-Trees easy or hard?

The problem is rated Medium because the OR logic itself is simple but the quad-tree merging and compression rules require careful implementation. Candidates must correctly handle leaf cases, recursive quadrant merging, and post-merge compression. Understanding tree recursion makes the solution straightforward.

Logical OR of Two Binary Grids Represented as Quad-Trees Python/Java solution

Python and Java implementations typically use a recursive helper function that accepts two nodes and returns the merged node. The function handles base cases for leaf nodes, recursively merges child quadrants, and compresses identical children into a single leaf node. Both implementations achieve O(n) time complexity with clean tree recursion.

How to solve Logical OR of Two Binary Grids Represented as Quad-Trees in O(n)?

Traverse both quad-trees simultaneously and merge corresponding nodes. If either node is a leaf with value 1, return a leaf 1 for that region because OR(1, x) is always 1. Otherwise recursively merge the four child quadrants and compress them if all children become identical leaf nodes. Each node pair is processed once, giving O(n) time complexity.

What is the best approach for Logical OR of Two Binary Grids Represented as Quad-Trees?

The recursive quad-tree merge approach is the most practical solution. It compares corresponding nodes from both trees and applies the logical OR rule while recursively merging child quadrants. If either node is a leaf with value 1, the result becomes a leaf 1 immediately. This method runs in O(n) time and uses O(h) recursion stack space, where h is the tree height.

Is Logical OR of Two Binary Grids Represented as Quad-Trees asked at Google/Amazon/Meta?

Quad-tree and divide-and-conquer problems appear in interviews at companies like Google, Amazon, and Meta when discussing spatial data structures or hierarchical grids. Variants of this problem test recursive tree merging and compression logic. The problem focuses on reasoning about tree structures rather than complex algorithms.

What data structure is used in Logical OR of Two Binary Grids Represented as Quad-Trees?

The primary data structure is a quad-tree, a hierarchical tree where each internal node has exactly four children representing quadrants of a grid. The algorithm also uses recursion or an explicit stack for traversal. Quad-trees are commonly used in spatial indexing, image compression, and grid partitioning problems.

What is the time complexity of Logical OR of Two Binary Grids Represented as Quad-Trees?

The optimal time complexity is O(n), where n is the total number of nodes visited across both quad-trees. Each pair of nodes is processed at most once while merging the four quadrants. Space complexity is O(h) for the recursive stack or O(n) for the iterative stack-based traversal.

Logical OR of Two Binary Grids Represented as Quad-Trees solution and explanation

The problem

Approach overview

Approach 1: Recursive Merge of Quad-Trees

Approach 2: Iterative Post-Order Traversal Using Stack

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Logical OR of Two Binary Grids Represented as Quad-Trees solution and explanation

The problem

Approach overview

Approach 1: Recursive Merge of Quad-Trees

Approach 2: Iterative Post-Order Traversal Using Stack

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems