Logical OR of Two Binary Grids Represented as Quad-Trees

Logical OR of Two Binary Grids Represented as Quad-Trees - 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 matrices represented by quadTree1 and quadTree2.

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.

Quad-Tree Construction Rules:

If the current grid has the same value (all 1's or all 0's), set isLeaf to True and set val to the value of the grid.
If the current grid has different values, set isLeaf to False and divide the current grid into four sub-grids: topLeft, topRight, bottomLeft, bottomRight.

Input & Output

Example 1 — Basic OR Operation

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

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

💡 Note: First tree represents [[0,1],[1,1]], second tree represents [[1,1],[1,0]]. OR operation results in [[1,1],[1,1]] which becomes a single leaf node with value 1.

Example 2 — Single Cell Trees

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

› Output: [[1,1]]

💡 Note: Both trees represent single cells: 0 OR 1 = 1. Result is a single leaf with value 1.

Example 3 — No Simplification Possible

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

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

💡 Note: Trees represent different patterns that when OR'ed together create a mixed result that cannot be simplified to a single leaf.

Constraints

quadTree1 and quadTree2 are both valid Quad-Trees
n == 2^x where 0 ≤ x ≤ 9
Both trees represent the same size grid

Visualization

Tap to expand

Understanding the Visualization

Input Trees

Two quad-trees representing binary matrices

OR Operation

Combine corresponding regions using logical OR

Result Tree

New quad-tree representing the OR'ed matrix

Key Takeaway

🎯 Key Insight: OR operation allows early termination when any region contains all 1's, making direct tree combination more efficient than matrix conversion

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to leverage the properties of the OR operation: if either quad-tree region contains all 1's, the result is all 1's. The direct recursive approach is optimal, combining trees without converting to matrices. Time: O(n²), Space: O(log n)

Common Approaches

Approach	Time	Space	Notes
✓ Direct Recursive OR	O(n²)	O(log n)	Recursively combine quad-trees using divide and conquer
Matrix Conversion Approach	O(n²)	O(n²)	Convert quad-trees to matrices, perform OR operation, rebuild quad-tree

Direct Recursive OR — Algorithm Steps

Step 1: Check if either tree has all 1's (early termination)
Step 2: If both are leaves, OR their values
Step 3: Recursively combine corresponding children
Step 4: Check if result children can be merged into a single leaf

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare Roots

Check if either root is a leaf with value true

Recursive Combine

Recursively OR corresponding children

Merge Check

Check if result children can be simplified

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct Node {
    bool val;
    bool isLeaf;
    struct Node* topLeft;
    struct Node* topRight;
    struct Node* bottomLeft;
    struct Node* bottomRight;
};

struct Node* createNode(bool val, bool isLeaf) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->val = val;
    node->isLeaf = isLeaf;
    node->topLeft = NULL;
    node->topRight = NULL;
    node->bottomLeft = NULL;
    node->bottomRight = NULL;
    return node;
}

struct Node* solution(struct Node* quadTree1, struct Node* quadTree2) {
    // If either tree represents all 1's, result is all 1's
    if (quadTree1->isLeaf) {
        return quadTree1->val ? quadTree1 : quadTree2;
    }
    if (quadTree2->isLeaf) {
        return quadTree2->val ? quadTree2 : quadTree1;
    }
    
    // Both are internal nodes, recursively combine children
    struct Node* topLeft = solution(quadTree1->topLeft, quadTree2->topLeft);
    struct Node* topRight = solution(quadTree1->topRight, quadTree2->topRight);
    struct Node* bottomLeft = solution(quadTree1->bottomLeft, quadTree2->bottomLeft);
    struct Node* bottomRight = solution(quadTree1->bottomRight, quadTree2->bottomRight);
    
    // Check if all children are leaves with same value
    if (topLeft->isLeaf && topRight->isLeaf && 
        bottomLeft->isLeaf && bottomRight->isLeaf &&
        topLeft->val == topRight->val && topLeft->val == bottomLeft->val && topLeft->val == bottomRight->val) {
        return createNode(topLeft->val, true);
    }
    
    struct Node* result = createNode(false, false);
    result->topLeft = topLeft;
    result->topRight = topRight;
    result->bottomLeft = bottomLeft;
    result->bottomRight = bottomRight;
    
    return result;
}

int main() {
    // Input parsing would go here for actual implementation
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

In worst case, need to visit all nodes representing n² cells

⚠ Quadratic Growth

Space Complexity

O(log n)

Recursion depth is at most log₄(n) for balanced quad-tree

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Direct Recursive OR — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler