Leetcode - 427. Construct Quad Tree

QuadTrees are a fascinating data structure, often used in image compression, spatial indexing, and graphics. In this blog, we’ll solve the LeetCode 427 – Construct Quad Tree problem, step by step.

---

📌 Problem Statement

You are given an n x n binary grid (only 0 and 1 values).

Your task is to construct a QuadTree based on this grid:

• Each node in the tree represents a sub-square of the grid.
• If the sub-square contains all the same values (0 or 1), it becomes a leaf node.

• Otherwise, it splits into four children:

  • topLeft
  • topRight
  • bottomLeft
  • bottomRight

---

📖 What is a QuadTree?

A QuadTree recursively divides a 2D space into four quadrants.

For example, take this 4x4 binary grid:

1 1 0 0
1 1 0 0
0 0 1 1
0 0 1 1

• The top-left 2x2 block is all 1 → becomes a leaf node.
• The top-right 2x2 block is all 0 → another leaf node.
• The bottom-left 2x2 block is all 0.
• The bottom-right 2x2 block is all 1.

So the root node will split into four leaves.

---

🛠️ Approach

We’ll use DFS (divide and conquer) to recursively build the tree:

1. Check if the current sub-square is uniform (all values are the same).

• If yes → return a leaf node.
• If not → split into four quadrants.

1. Recursive Subdivision:

• Divide the current square of size n into four n/2 quadrants.
• Recursively construct the QuadTree for each.

1. Build the Node:

• If it’s a leaf → isLeaf = true.
• If not → isLeaf = false and link four children.

---

✅ Solution Code

/**
 * // Definition for a QuadTree node.
 * function Node(val, isLeaf, topLeft, topRight, bottomLeft, bottomRight) {
 *    this.val = val;
 *    this.isLeaf = isLeaf;
 *    this.topLeft = topLeft;
 *    this.topRight = topRight;
 *    this.bottomLeft = bottomLeft;
 *    this.bottomRight = bottomRight;
 * };
 */

/**
 * @param {number[][]} grid
 * @return {Node}
 */
var construct = function (grid) {

    const dfs = (n, r, c) => {
        let isAllSame = true;
        let firstVal = grid[r][c];

        // check if all values in current n x n block are the same
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (grid[r + i][c + j] !== firstVal) {
                    isAllSame = false;
                    break;
                }
            }
            if (!isAllSame) break;
        }

        // case 1: all same → leaf node
        if (isAllSame) {
            return new Node(firstVal === 1, true, null, null, null, null);
        }

        // case 2: not uniform → divide into 4 parts
        let half = Math.floor(n / 2);
        let topLeftNode = dfs(half, r, c);
        let topRightNode = dfs(half, r, c + half);
        let bottomLeftNode = dfs(half, r + half, c);
        let bottomRightNode = dfs(half, r + half, c + half);

        return new Node(true, false, topLeftNode, topRightNode, bottomLeftNode, bottomRightNode);
    };

    return dfs(grid.length, 0, 0);
};

---

⏱️ Complexity Analysis

Time Complexity

• At each level, we scan an n x n block to check if it’s uniform.
• Then we split into 4 subproblems of size n/2.

So recurrence:

T(n) = 4T(n/2) + O(n^2)

This looks like O(n^2 log n) in the worst case.
But since each cell is checked only once in practice, the overall complexity simplifies to O(n^2).

👉 This is optimal since we must inspect every cell at least once.

Space Complexity

• The recursion depth is O(log n) (each time we halve n).
• The QuadTree itself can take up to O(n^2) nodes in the worst case (checkerboard pattern).

So space complexity is O(n^2).

---

🎯 Key Takeaways

• QuadTrees are great for representing 2D uniform data efficiently.
• If a subgrid is uniform, we don’t need to store every cell → compression.
• Divide & conquer makes this problem elegant and intuitive.

---