Construct Quad Tree - Practice Coding Problems

Construct Quad Tree - Problem

Given an n × n matrix grid of 0's and 1's only, we want to represent the grid with a Quad-Tree.

Return the root of the Quad-Tree representing grid.

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. Notice that you can assign the val to True or False when isLeaf is False, and both are accepted in the answer.
isLeaf: True if the node is a leaf node on the tree or False if the node has four children.

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. Recurse for each of the children with the proper sub-grid.

Input & Output

Example 1 — Basic 2×2 Grid

$ Input: grid = [[1,1],[0,0]]

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

💡 Note: Top half is all 1's (uniform), bottom half is all 0's (uniform), so root has 4 children: top-left leaf(1), top-right leaf(1), bottom-left leaf(0), bottom-right leaf(0)

Example 2 — All Same Values

$ Input: grid = [[1,1],[1,1]]

› Output: [[1,1]]

💡 Note: Entire grid is uniform (all 1's), so we get a single leaf node with val=1 and isLeaf=1

Example 3 — Complex 4×4 Grid

$ Input: grid = [[1,1,0,0],[1,1,0,0],[1,1,1,1],[1,1,1,1]]

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

💡 Note: Top-left 2×2 is all 1's (leaf), top-right 2×2 is all 0's (leaf), bottom half is all 1's but gets subdivided first then merged

Constraints

n == grid.length == grid[i].length
n is a power of 2
1 ≤ n ≤ 64
grid[i][j] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Grid

2D matrix of 0s and 1s

Recursive Division

Split into 4 quadrants until uniform

Quad Tree

Tree with 4 children per internal node

Key Takeaway

🎯 Key Insight: Recursively divide mixed regions into quadrants until each area contains only 0s or only 1s

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to recursively divide the grid into quadrants until each region is uniform (all 0s or all 1s). Use divide and conquer approach with smart merging to create leaf nodes for uniform regions and internal nodes for mixed regions. Best approach is the optimized version with Time: O(n²), Space: O(log n).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Divide and Conquer	O(n²)	O(log n)	Directly divide regions without full scanning when possible
Brute Force - Check Every Cell	O(n² log n)	O(log n)	Check all cells in current region to determine if uniform

Optimized - Divide and Conquer — Algorithm Steps

Step 1: Check corner case for single cell (base case)
Step 2: Divide current region into 4 quadrants
Step 3: Recursively build quadrants and merge if all are uniform leaves

Visualization

Tap to expand

Step-by-Step Walkthrough

Base Case

Single cell becomes leaf node

Divide

Split into 4 quadrants recursively

Merge

Combine uniform children into single leaf

Code -

solution.c — C

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

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

struct Node* build(int** grid, int n, int r1, int c1, int r2, int c2) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    
    if (r2 - r1 == 1) {
        node->val = (grid[r1][c1] == 1);
        node->isLeaf = true;
        node->topLeft = node->topRight = node->bottomLeft = node->bottomRight = NULL;
        return node;
    }
    
    int midR = (r1 + r2) / 2;
    int midC = (c1 + c2) / 2;
    
    struct Node* topLeft = build(grid, n, r1, c1, midR, midC);
    struct Node* topRight = build(grid, n, r1, midC, midR, c2);
    struct Node* bottomLeft = build(grid, n, midR, c1, r2, midC);
    struct Node* bottomRight = build(grid, n, midR, midC, r2, c2);
    
    if (topLeft->isLeaf && topRight->isLeaf && 
        bottomLeft->isLeaf && bottomRight->isLeaf &&
        topLeft->val == topRight->val && 
        topLeft->val == bottomLeft->val && 
        topLeft->val == bottomRight->val) {
        node->val = topLeft->val;
        node->isLeaf = true;
        node->topLeft = node->topRight = node->bottomLeft = node->bottomRight = NULL;
        return node;
    }
    
    node->val = true;
    node->isLeaf = false;
    node->topLeft = topLeft;
    node->topRight = topRight;
    node->bottomLeft = bottomLeft;
    node->bottomRight = bottomRight;
    
    return node;
}

void printNode(struct Node* node) {
    if (node == NULL) {
        printf("null");
        return;
    }
    
    printf("[%d,%d", node->isLeaf ? 1 : 0, node->val ? 1 : 0);
    if (!node->isLeaf) {
        printf(",");
        printNode(node->topLeft);
        printf(",");
        printNode(node->topRight);
        printf(",");
        printNode(node->bottomLeft);
        printf(",");
        printNode(node->bottomRight);
    }
    printf("]");
}

struct Node* solution(int** grid, int n) {
    return build(grid, n, 0, 0, n, n);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int** grid = (int**)malloc(4 * sizeof(int*));
    for (int i = 0; i < 4; i++) {
        grid[i] = (int*)malloc(4 * sizeof(int));
    }
    
    sscanf(line, "[[%d,%d],[%d,%d]]", &grid[0][0], &grid[0][1], &grid[1][0], &grid[1][1]);
    
    struct Node* result = solution(grid, 2);
    printNode(result);
    printf("\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Each cell is processed exactly once during the recursive division

⚠ 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

876 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

Optimized - Divide and Conquer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler