Logical or of two binary grids represented as quad trees

Divide and Conquer Tree

52.4% acceptance

Jan 13, 2026

205

482

Given quadTree1 and quadTree2, each representing a n * n binary matrix. Return a Quad-Tree representing the logical bitwise OR of the two binary matrices.

Solution

C++

Time O(1)

Space O(1)

LeetCode

solution.cpp

class Solution {
public:
  Node* intersect(Node* q1, Node* q2) {
    if (q1->isLeaf) return q1->val ? q1 : q2;
    if (q2->isLeaf) return q2->val ? q2 : q1;
    Node* tl = intersect(q1->topLeft, q2->topLeft);
    Node* tr = intersect(q1->topRight, q2->topRight);
    Node* bl = intersect(q1->bottomLeft, q2->bottomLeft);
    Node* br = intersect(q1->bottomRight, q2->bottomRight);
    if (tl->isLeaf && tr->isLeaf && bl->isLeaf && br->isLeaf &&
      tl->val == tr->val && tr->val == bl->val && bl->val == br->val)
      return new Node(tl->val, true);
    return new Node(false, false, tl, tr, bl, br);
  }
};