Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

558. Logical OR of Two Binary Grids Represented as Quad-Trees - Leetcode Solution

Code Implementation

# Definition for a QuadTree node.
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

class Solution:
    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':
        if quadTree1.isLeaf:
            if quadTree1.val:
                return Node(True, True)
            else:
                return quadTree2
        if quadTree2.isLeaf:
            if quadTree2.val:
                return Node(True, True)
            else:
                return quadTree1
        tl = self.intersect(quadTree1.topLeft, quadTree2.topLeft)
        tr = self.intersect(quadTree1.topRight, quadTree2.topRight)
        bl = self.intersect(quadTree1.bottomLeft, quadTree2.bottomLeft)
        br = self.intersect(quadTree1.bottomRight, quadTree2.bottomRight)
        # If all children are leaves and have the same value, merge them
        if tl.isLeaf and tr.isLeaf and bl.isLeaf and br.isLeaf and \
           tl.val == tr.val == bl.val == br.val:
            return Node(tl.val, True)
        return Node(False, False, tl, tr, bl, br)
      
/*
// 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) {
        if (quadTree1->isLeaf) {
            if (quadTree1->val) return new Node(true, true);
            else return quadTree2;
        }
        if (quadTree2->isLeaf) {
            if (quadTree2->val) return new Node(true, true);
            else return quadTree1;
        }
        Node* tl = intersect(quadTree1->topLeft, quadTree2->topLeft);
        Node* tr = intersect(quadTree1->topRight, quadTree2->topRight);
        Node* bl = intersect(quadTree1->bottomLeft, quadTree2->bottomLeft);
        Node* br = intersect(quadTree1->bottomRight, quadTree2->bottomRight);
        if (tl->isLeaf && tr->isLeaf && bl->isLeaf && br->isLeaf &&
            tl->val == tr->val && tl->val == bl->val && tl->val == br->val) {
            return new Node(tl->val, true);
        }
        return new Node(false, false, tl, tr, bl, br);
    }
};
      
/*
// Definition for a QuadTree node.
class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;

    public Node() {}
    public Node(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
    }
    public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
};
*/

class Solution {
    public Node intersect(Node quadTree1, Node quadTree2) {
        if (quadTree1.isLeaf) {
            if (quadTree1.val) return new Node(true, true);
            else return quadTree2;
        }
        if (quadTree2.isLeaf) {
            if (quadTree2.val) return new Node(true, true);
            else return quadTree1;
        }
        Node tl = intersect(quadTree1.topLeft, quadTree2.topLeft);
        Node tr = intersect(quadTree1.topRight, quadTree2.topRight);
        Node bl = intersect(quadTree1.bottomLeft, quadTree2.bottomLeft);
        Node br = intersect(quadTree1.bottomRight, quadTree2.bottomRight);
        if (tl.isLeaf && tr.isLeaf && bl.isLeaf && br.isLeaf &&
            tl.val == tr.val && tl.val == bl.val && tl.val == br.val) {
            return new Node(tl.val, true);
        }
        return new Node(false, false, tl, tr, bl, br);
    }
}
      
/*
class Node {
    constructor(val, isLeaf, topLeft, topRight, bottomLeft, bottomRight) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
}
*/

var intersect = function(quadTree1, quadTree2) {
    if (quadTree1.isLeaf) {
        if (quadTree1.val) return new Node(true, true);
        else return quadTree2;
    }
    if (quadTree2.isLeaf) {
        if (quadTree2.val) return new Node(true, true);
        else return quadTree1;
    }
    let tl = intersect(quadTree1.topLeft, quadTree2.topLeft);
    let tr = intersect(quadTree1.topRight, quadTree2.topRight);
    let bl = intersect(quadTree1.bottomLeft, quadTree2.bottomLeft);
    let br = intersect(quadTree1.bottomRight, quadTree2.bottomRight);
    if (tl.isLeaf && tr.isLeaf && bl.isLeaf && br.isLeaf &&
        tl.val === tr.val && tl.val === bl.val && tl.val === br.val) {
        return new Node(tl.val, true);
    }
    return new Node(false, false, tl, tr, bl, br);
};

Problem Description

You are given two binary grids, each represented as a quad-tree. Each quad-tree node contains:

  • val: a boolean indicating the value of the region (True for 1, False for 0)
  • isLeaf: a boolean indicating whether the node is a leaf (i.e., represents a uniform region)
  • topLeft, topRight, bottomLeft, bottomRight: pointers to the four child nodes (if not a leaf)
Your task is to compute the quad-tree representing the logical OR of the two input quad-trees. The OR operation is performed region-wise: for each cell in the grid, the value is 1 if it is 1 in at least one of the two grids.

The output must also be a quad-tree in the same format. You may merge nodes if all four children are leaves and have the same value. The input quad-trees are valid and represent grids of the same size.

Thought Process

At first glance, this problem might seem to require converting the quad-trees back to grids, performing the OR operation cell by cell, and then constructing a new quad-tree. However, this would be inefficient and unnecessary. Instead, we can take advantage of the recursive, hierarchical nature of quad-trees.

The key insight is that the logical OR operation can be performed directly on the quad-tree nodes:

  • If either node is a leaf with value 1 (True), the result for that region is 1 (True) regardless of the other node.
  • If one node is a leaf with value 0 (False), the result is determined entirely by the other node.
  • If both nodes are internal (not leaves), recursively compute the OR for each of the four corresponding child regions.
This recursive approach mirrors how quad-trees partition the space, allowing us to combine the grids efficiently without ever expanding them to full matrices.

Solution Approach

  • Base Case - Leaf Nodes:
    • If the first node is a leaf and its value is 1, the result is a leaf with value 1 (since OR with 1 is always 1).
    • If the first node is a leaf with value 0, the result is the second node (since OR with 0 doesn't change the other value).
    • Symmetrically, if the second node is a leaf, apply the same logic.
  • Recursive Case - Internal Nodes:
    • If both nodes are internal (not leaves), recursively OR their corresponding children: topLeft with topLeft, topRight with topRight, etc.
    • After getting the four child results, check if all four are leaves with the same value. If so, merge them into a single leaf node for compression.
    • If not, create a new internal node with these four children.
  • Why This Works:
    • This approach leverages the quad-tree's recursive structure and only expands nodes as needed, avoiding unnecessary work.
    • Merging uniform regions keeps the resulting tree compact.

Example Walkthrough

Let's walk through a simple example:
Suppose quadTree1 is a leaf node representing a 2x2 region of all 0s (val=False, isLeaf=True).
quadTree2 is an internal node with four children:

  • topLeft: leaf, value 1
  • topRight: leaf, value 0
  • bottomLeft: leaf, value 0
  • bottomRight: leaf, value 1
Step-by-step:
  1. Since quadTree1 is a leaf with value 0, return quadTree2 as the result (since OR with 0 leaves the other unchanged).
  2. The result is an internal node with the same children as quadTree2.

Now, if quadTree1 were a leaf with value 1, the result would be a single leaf node with value 1, since OR with 1 is always 1.

For more complex trees, the recursion would continue, comparing and combining corresponding children at each level.

Time and Space Complexity

  • Brute-force approach:
    • Convert both quad-trees to full grids of size N x N, perform cell-wise OR, then build a new quad-tree: O(N2) time and space.
  • Optimized recursive approach (as implemented):
    • Let n be the number of nodes in the two trees. In the worst case, each node is visited once, so time complexity is O(n).
    • Space complexity is O(h), where h is the height of the trees, due to recursion stack (plus space for the new tree, which is at most O(n)).
    • This is much better than the brute-force approach, especially for sparse or highly compressible grids.

Summary

The key to solving the Logical OR of Two Binary Grids Represented as Quad-Trees is to use the recursive structure of quad-trees to perform the operation efficiently. By handling leaf nodes as base cases and recursively combining internal nodes, we avoid unnecessary expansion to full grids and keep the tree compact by merging uniform regions. This approach is both elegant and efficient, making optimal use of the quad-tree's properties.