Logical OR of Two Binary Grids Represented as Quad-Trees

medium tree divide and conquer

Problem

Two quad-trees represent two n×n binary grids. Return the quad-tree of the OR'd grid.

Inputqt1=[[0,1],[1,1],[1,1],[1,0],[1,0]], qt2=[[0,1],[1,1],[0,1],[1,1],[1,0]]

OutputOR'd quad-tree

Recursion: any leaf 1 short-circuits; collapse when all four children become identical leaves.

grid1 (rows ; ,)

grid2 (rows ; ,)

class Node:
    def __init__(self, val=False, isLeaf=False, tl=None, tr=None, bl=None, br=None):
        self.val = val; self.isLeaf = isLeaf
        self.tl = tl; self.tr = tr; self.bl = bl; self.br = br
def intersect(t1, t2):
    if t1.isLeaf: return t1 if t1.val else t2
    if t2.isLeaf: return t2 if t2.val else t1
    tl = intersect(t1.tl, t2.tl); tr = intersect(t1.tr, t2.tr)
    bl = intersect(t1.bl, t2.bl); br = intersect(t1.br, t2.br)
    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)

class Node {
  constructor(val, isLeaf, tl = null, tr = null, bl = null, br = null) {
    this.val = val; this.isLeaf = isLeaf;
    this.topLeft = tl; this.topRight = tr; this.bottomLeft = bl; this.bottomRight = br;
  }
}
function intersect(t1, t2) {
  if (t1.isLeaf) return t1.val ? t1 : t2;
  if (t2.isLeaf) return t2.val ? t2 : t1;
  const tl = intersect(t1.topLeft, t2.topLeft);
  const tr = intersect(t1.topRight, t2.topRight);
  const bl = intersect(t1.bottomLeft, t2.bottomLeft);
  const br = intersect(t1.bottomRight, t2.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);
}

class Solution {
    public Node intersect(Node t1, Node t2) {
        if (t1.isLeaf) return t1.val ? t1 : t2;
        if (t2.isLeaf) return t2.val ? t2 : t1;
        Node tl = intersect(t1.topLeft, t2.topLeft);
        Node tr = intersect(t1.topRight, t2.topRight);
        Node bl = intersect(t1.bottomLeft, t2.bottomLeft);
        Node br = intersect(t1.bottomRight, t2.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);
    }
}

Node* intersect(Node* t1, Node* t2) {
    if (t1->isLeaf) return t1->val ? t1 : t2;
    if (t2->isLeaf) return t2->val ? t2 : t1;
    Node* tl = intersect(t1->topLeft, t2->topLeft);
    Node* tr = intersect(t1->topRight, t2->topRight);
    Node* bl = intersect(t1->bottomLeft, t2->bottomLeft);
    Node* br = intersect(t1->bottomRight, t2->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);
}

Explanation

A quad-tree stores a square grid by recursively splitting it into four quadrants until each region is all 0 or all 1 (a leaf). To OR two such grids, we recurse on the matching quadrants of both trees together.

The shortcuts come from how OR behaves on a leaf. If t1 is a leaf with value 1, then that whole region is 1 regardless of t2, so we return t1. If t1 is a leaf with value 0, OR-ing with t2 leaves t2 unchanged, so we return t2. The same two rules apply when t2 is the leaf.

If neither side is a leaf, we recurse on all four children (top-left, top-right, bottom-left, bottom-right). After combining, we try to collapse: if all four results are leaves with the same value, that region is uniform, so we merge them into one leaf. Otherwise we keep the four children as an internal node.

Example: in one quadrant t1 is a solid 1 leaf. We immediately return it without even looking inside t2, because anything OR 1 is 1. Elsewhere, four mixed children that all reduce to 1 get folded back into a single 1 leaf.

Each cell of the n×n grid is touched a constant number of times, so the work is about O(n²).

Time: O(n²) Space: O(n²)