Construct Quad Tree

Problem Statement

Given an n × n matrix of 0s and 1s, construct a quad tree with the following rules:

1. If all values in a region are the same, create a leaf node with that value.
2. Otherwise, subdivide the region into 4 equal quadrants (top-left, top-right, bottom-left, bottom-right) and recursively build the tree.

What to notice first

• Pure divide and conquer: divide into 4 quadrants recursively.
• Base case: all values in a quadrant are the same → leaf node.
• Recursive case: quadrant has mixed values → subdivide further.
• Early termination when homogeneous regions are found.

Examples

Input	Output
[[1,1],[1,0]]	Quad tree with non-leaf root, mixed children
[[1,1],[1,1]]	Single leaf node with val=true

Constraints

• n == 2^x where 0 <= x <= 6
• grid[i][j] is either 0 or 1

Real-World Applications

Where this pattern appears

• File system hierarchies and directory structures
• DOM tree manipulation in web browsers
• XML/JSON parsing and configuration management
• Organizational hierarchies and permission trees

Complexity Comparison

Approach	Time	Space
Recursive	O(n² log n)	O(log n)
Iterative	O(n² log n)	O(n² / 4)

Which approach should you learn first?

• Pick Recursive for clarity — pure divide and conquer pattern.
• Pick Iterative if you prefer explicit queue management.

Natural Fit

Recursive

O(n² log n) time · O(log n) space

Explicit Queue

Iterative

O(n² log n) time · O(n²) space

Approach 1: Recursive Divide and Conquer (Recommended)

★ Recommended

1. Check if all values in the current region are the same.
2. If yes, create a leaf node.
3. If no, create a non-leaf node and recursively subdivide into 4 quadrants.

⏱ Time O(n² log n) Worst case exploration 💾 Space O(log n) Recursion depth

Solution Code

Python

construct_quad_tree_recursive.py

from typing import List

class Node:
    def __init__(self, val, isLeaf, topLeft=None, topRight=None, bottomLeft=None, bottomRight=None):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight

def construct(grid: List[List[int]]) -> 'Node':
    def dfs(top, left, size):
        all_same = True
        val = grid[top][left]

        for i in range(top, top + size):
            for j in range(left, left + size):
                if grid[i][j] != val:
                    all_same = False
                    break
            if not all_same:
                break

        if all_same:
            return Node(val == 1, True)

        half = size // 2
        topLeft = dfs(top, left, half)
        topRight = dfs(top, left + half, half)
        bottomLeft = dfs(top + half, left, half)
        bottomRight = dfs(top + half, left + half, half)

        return Node(1, False, topLeft, topRight, bottomLeft, bottomRight)

    return dfs(0, 0, len(grid))

grid = [[1,1],[1,0]]
root = construct(grid)
print(root.val, root.isLeaf)

C++

construct_quad_tree_recursive.cpp

#include <iostream>
#include <vector>

class Node {
public:
    bool val;
    bool isLeaf;
    Node* topLeft;
    Node* topRight;
    Node* bottomLeft;
    Node* bottomRight;

    Node(bool val, bool isLeaf) : val(val), isLeaf(isLeaf), topLeft(nullptr), topRight(nullptr), bottomLeft(nullptr), bottomRight(nullptr) {}
};

Node* construct(std::vector<std::vector<int>>& grid, int top, int left, int size) {
    bool all_same = true;
    int val = grid[top][left];

    for (int i = top; i < top + size && all_same; i++) {
        for (int j = left; j < left + size && all_same; j++) {
            if (grid[i][j] != val) all_same = false;
        }
    }

    if (all_same) return new Node(val == 1, true);

    int half = size / 2;
    Node* node = new Node(1, false);
    node->topLeft = construct(grid, top, left, half);
    node->topRight = construct(grid, top, left + half, half);
    node->bottomLeft = construct(grid, top + half, left, half);
    node->bottomRight = construct(grid, top + half, left + half, half);
    return node;
}

Node* construct(std::vector<std::vector<int>>& grid) {
    return construct(grid, 0, 0, grid.size());
}

int main() {
    std::vector<std::vector<int>> grid = {{1, 1}, {1, 0}};
    Node* root = construct(grid);
    std::cout << root->val << " " << root->isLeaf << std::endl;
    return 0;
}

Java

ConstructQuadTree_Recursive.java

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;

    public Node(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
    }
}

class Solution {
    public Node construct(int[][] grid) {
        return dfs(grid, 0, 0, grid.length);
    }

    private Node dfs(int[][] grid, int top, int left, int size) {
        boolean allSame = true;
        int val = grid[top][left];

        for (int i = top; i < top + size && allSame; i++) {
            for (int j = left; j < left + size && allSame; j++) {
                if (grid[i][j] != val) allSame = false;
            }
        }

        if (allSame) return new Node(val == 1, true);

        int half = size / 2;
        Node node = new Node(true, false);
        node.topLeft = dfs(grid, top, left, half);
        node.topRight = dfs(grid, top, left + half, half);
        node.bottomLeft = dfs(grid, top + half, left, half);
        node.bottomRight = dfs(grid, top + half, left + half, half);
        return node;
    }
}

public class ConstructQuadTree_Recursive {
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] grid = {{1, 1}, {1, 0}};
        Node root = sol.construct(grid);
        System.out.println(root.val + " " + root.isLeaf);
    }
}

JavaScript

construct_quad_tree_recursive.js

class Node {
    constructor(val, isLeaf, topLeft = null, topRight = null, bottomLeft = null, bottomRight = null) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
}

function construct(grid) {
    function dfs(top, left, size) {
        let allSame = true;
        const val = grid[top][left];

        for (let i = top; i < top + size && allSame; i++) {
            for (let j = left; j < left + size && allSame; j++) {
                if (grid[i][j] !== val) allSame = false;
            }
        }

        if (allSame) return new Node(val === 1, true);

        const half = Math.floor(size / 2);
        const node = new Node(true, false);
        node.topLeft = dfs(top, left, half);
        node.topRight = dfs(top, left + half, half);
        node.bottomLeft = dfs(top + half, left, half);
        node.bottomRight = dfs(top + half, left + half, half);
        return node;
    }

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

const grid = [[1, 1], [1, 0]];
const root = construct(grid);
console.log(root.val, root.isLeaf);

Rust

construct_quad_tree_recursive.rs

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
pub struct Node {
    pub val: i32,
    pub is_leaf: bool,
    pub top_left: Option<Rc<RefCell<Node>>>,
    pub top_right: Option<Rc<RefCell<Node>>>,
    pub bottom_left: Option<Rc<RefCell<Node>>>,
    pub bottom_right: Option<Rc<RefCell<Node>>>,
}

impl Node {
    fn new(val: i32, is_leaf: bool) -> Self {
        Node {
            val,
            is_leaf,
            top_left: None,
            top_right: None,
            bottom_left: None,
            bottom_right: None,
        }
    }
}

fn construct(grid: Vec<Vec<i32>>) -> Option<Rc<RefCell<Node>>> {
    fn dfs(grid: &Vec<Vec<i32>>, top: usize, left: usize, size: usize) -> Option<Rc<RefCell<Node>>> {
        let val = grid[top][left];
        let mut all_same = true;

        for i in top..top + size {
            for j in left..left + size {
                if grid[i][j] != val {
                    all_same = false;
                    break;
                }
            }
            if !all_same {
                break;
            }
        }

        if all_same {
            Some(Rc::new(RefCell::new(Node::new(if val == 1 { 1 } else { 0 }, true))))
        } else {
            let half = size / 2;
            let mut node = Node::new(1, false);
            node.top_left = dfs(grid, top, left, half);
            node.top_right = dfs(grid, top, left + half, half);
            node.bottom_left = dfs(grid, top + half, left, half);
            node.bottom_right = dfs(grid, top + half, left + half, half);
            Some(Rc::new(RefCell::new(node)))
        }
    }

    dfs(&grid, 0, 0, grid.len())
}

fn main() {
    let grid = vec![vec![1, 1], vec![1, 0]];
    let root = construct(grid);
    if let Some(r) = root {
        println!("{} {}", r.borrow().val, r.borrow().is_leaf);
    }
}

Go

construct_quad_tree_recursive.go

package main

import "fmt"

type Node struct {
  Val         bool
  IsLeaf      bool
  TopLeft     *Node
  TopRight    *Node
  BottomLeft  *Node
  BottomRight *Node
}

func construct(grid [][]int) *Node {
  return dfs(grid, 0, 0, len(grid))
}

func dfs(grid [][]int, top, left, size int) *Node {
  allSame := true
  val := grid[top][left]

  for i := top; i < top+size && allSame; i++ {
    for j := left; j < left+size && allSame; j++ {
      if grid[i][j] != val {
        allSame = false
      }
    }
  }

  if allSame {
    return &Node{Val: val == 1, IsLeaf: true}
  }

  half := size / 2
  node := &Node{Val: true, IsLeaf: false}
  node.TopLeft = dfs(grid, top, left, half)
  node.TopRight = dfs(grid, top, left+half, half)
  node.BottomLeft = dfs(grid, top+half, left, half)
  node.BottomRight = dfs(grid, top+half, left+half, half)
  return node
}

func main() {
  grid := [][]int{{1, 1}, {1, 0}}
  root := construct(grid)
  fmt.Println(root.Val, root.IsLeaf)
}

Approach 2: Iterative with Queue

🎯 Interview Favourite

Use a queue to track regions to subdivide. Process each region, check homogeneity, and enqueue children if needed.

⏱ Time O(n² log n) Worst case exploration 💾 Space O(n²) Queue storage

Solution Code

Python

construct_quad_tree_iterative.py

from typing import List
from collections import deque

class Node:
    def __init__(self, val, isLeaf, topLeft=None, topRight=None, bottomLeft=None, bottomRight=None):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight

def construct(grid: List[List[int]]) -> 'Node':
    n = len(grid)
    queue = deque([(0, 0, n, None)])
    root = None

    while queue:
        top, left, size, parent = queue.popleft()

        all_same = True
        val = grid[top][left]

        for i in range(top, top + size):
            for j in range(left, left + size):
                if grid[i][j] != val:
                    all_same = False
                    break
            if not all_same:
                break

        node = Node(val == 1, all_same)

        if root is None:
            root = node

        if not all_same:
            half = size // 2
            queue.append((top, left, half, node))
            queue.append((top, left + half, half, node))
            queue.append((top + half, left, half, node))
            queue.append((top + half, left + half, half, node))

    return root

grid = [[1,1],[1,0]]
root = construct(grid)
print(root.val, root.isLeaf)

C++

construct_quad_tree_iterative.cpp

#include <iostream>
#include <vector>
#include <queue>

class Node {
public:
    bool val;
    bool isLeaf;
    Node* topLeft;
    Node* topRight;
    Node* bottomLeft;
    Node* bottomRight;

    Node(bool val, bool isLeaf) : val(val), isLeaf(isLeaf), topLeft(nullptr), topRight(nullptr), bottomLeft(nullptr), bottomRight(nullptr) {}
};

Node* construct(std::vector<std::vector<int>>& grid) {
    int n = grid.size();
    struct Task { int top, left, size; Node* parent; };
    std::queue<Task> q;
    q.push({0, 0, n, nullptr});
    Node* root = nullptr;

    while (!q.empty()) {
        Task task = q.front();
        q.pop();

        bool all_same = true;
        int val = grid[task.top][task.left];
        for (int i = task.top; i < task.top + task.size && all_same; i++) {
            for (int j = task.left; j < task.left + task.size && all_same; j++) {
                if (grid[i][j] != val) all_same = false;
            }
        }

        Node* node = new Node(val == 1, all_same);
        if (root == nullptr) root = node;

        if (!all_same) {
            int half = task.size / 2;
            q.push({task.top, task.left, half, node});
            q.push({task.top, task.left + half, half, node});
            q.push({task.top + half, task.left, half, node});
            q.push({task.top + half, task.left + half, half, node});
        }
    }
    return root;
}

int main() {
    std::vector<std::vector<int>> grid = {{1, 1}, {1, 0}};
    Node* root = construct(grid);
    std::cout << root->val << " " << root->isLeaf << std::endl;
    return 0;
}

Java

ConstructQuadTree_Iterative.java

import java.util.*;

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;

    public Node(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
    }
}

class Solution {
    public Node construct(int[][] grid) {
        int n = grid.length;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, n});
        Node root = null;

        while (!queue.isEmpty()) {
            int[] task = queue.poll();
            int top = task[0], left = task[1], size = task[2];

            boolean allSame = true;
            int val = grid[top][left];
            for (int i = top; i < top + size && allSame; i++) {
                for (int j = left; j < left + size && allSame; j++) {
                    if (grid[i][j] != val) allSame = false;
                }
            }

            Node node = new Node(val == 1, allSame);
            if (root == null) root = node;

            if (!allSame) {
                int half = size / 2;
                queue.offer(new int[]{top, left, half});
                queue.offer(new int[]{top, left + half, half});
                queue.offer(new int[]{top + half, left, half});
                queue.offer(new int[]{top + half, left + half, half});
            }
        }
        return root;
    }
}

public class ConstructQuadTree_Iterative {
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] grid = {{1, 1}, {1, 0}};
        Node root = sol.construct(grid);
        System.out.println(root.val + " " + root.isLeaf);
    }
}

JavaScript

construct_quad_tree_iterative.js

class Node {
    constructor(val, isLeaf, topLeft = null, topRight = null, bottomLeft = null, bottomRight = null) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
}

function construct(grid) {
    const n = grid.length;
    const queue = [[0, 0, n]];
    let root = null;

    while (queue.length > 0) {
        const [top, left, size] = queue.shift();

        let allSame = true;
        const val = grid[top][left];
        for (let i = top; i < top + size && allSame; i++) {
            for (let j = left; j < left + size && allSame; j++) {
                if (grid[i][j] !== val) allSame = false;
            }
        }

        const node = new Node(val === 1, allSame);
        if (root === null) root = node;

        if (!allSame) {
            const half = Math.floor(size / 2);
            queue.push([top, left, half]);
            queue.push([top, left + half, half]);
            queue.push([top + half, left, half]);
            queue.push([top + half, left + half, half]);
        }
    }
    return root;
}

const grid = [[1, 1], [1, 0]];
const root = construct(grid);
console.log(root.val, root.isLeaf);

Rust

construct_quad_tree_iterative.rs

use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;

#[derive(Debug)]
pub struct Node {
    pub val: i32,
    pub is_leaf: bool,
    pub top_left: Option<Rc<RefCell<Node>>>,
    pub top_right: Option<Rc<RefCell<Node>>>,
    pub bottom_left: Option<Rc<RefCell<Node>>>,
    pub bottom_right: Option<Rc<RefCell<Node>>>,
}

impl Node {
    fn new(val: i32, is_leaf: bool) -> Self {
        Node {
            val,
            is_leaf,
            top_left: None,
            top_right: None,
            bottom_left: None,
            bottom_right: None,
        }
    }
}

fn construct(grid: Vec<Vec<i32>>) -> Option<Rc<RefCell<Node>>> {
    let n = grid.len();
    let mut queue: VecDeque<(usize, usize, usize)> = VecDeque::new();
    queue.push_back((0, 0, n));
    let mut root: Option<Rc<RefCell<Node>>> = None;

    while let Some((top, left, size)) = queue.pop_front() {
        let val = grid[top][left];
        let mut all_same = true;

        for i in top..top + size {
            for j in left..left + size {
                if grid[i][j] != val {
                    all_same = false;
                    break;
                }
            }
            if !all_same {
                break;
            }
        }

        let node = Rc::new(RefCell::new(Node::new(if val == 1 { 1 } else { 0 }, all_same)));

        if root.is_none() {
            root = Some(Rc::clone(&node));
        }

        if !all_same {
            let half = size / 2;
            queue.push_back((top, left, half));
            queue.push_back((top, left + half, half));
            queue.push_back((top + half, left, half));
            queue.push_back((top + half, left + half, half));
        }
    }

    root
}

fn main() {
    let grid = vec![vec![1, 1], vec![1, 0]];
    let root = construct(grid);
    if let Some(r) = root {
        println!("{} {}", r.borrow().val, r.borrow().is_leaf);
    }
}

Go

construct_quad_tree_iterative.go

package main

import (
  "fmt"
  "container/list"
)

type Node struct {
  Val         bool
  IsLeaf      bool
  TopLeft     *Node
  TopRight    *Node
  BottomLeft  *Node
  BottomRight *Node
}

func construct(grid [][]int) *Node {
  n := len(grid)
  type Task struct {
    top, left, size int
  }

  queue := list.New()
  queue.PushBack(Task{0, 0, n})
  var root *Node

  for queue.Len() > 0 {
    elem := queue.Front()
    queue.Remove(elem)
    task := elem.Value.(Task)

    allSame := true
    val := grid[task.top][task.left]
    for i := task.top; i < task.top+task.size && allSame; i++ {
      for j := task.left; j < task.left+task.size && allSame; j++ {
        if grid[i][j] != val {
          allSame = false
        }
      }
    }

    node := &Node{Val: val == 1, IsLeaf: allSame}
    if root == nil {
      root = node
    }

    if !allSame {
      half := task.size / 2
      queue.PushBack(Task{task.top, task.left, half})
      queue.PushBack(Task{task.top, task.left + half, half})
      queue.PushBack(Task{task.top + half, task.left, half})
      queue.PushBack(Task{task.top + half, task.left + half, half})
    }
  }

  return root
}

func main() {
  grid := [][]int{{1, 1}, {1, 0}}
  root := construct(grid)
  fmt.Println(root.Val, root.IsLeaf)
}

Common mistakes

Watch for these pitfalls

• Incorrect homogeneity check (must check entire region, not just corners).
• Wrong quadrant assignment (remember row-major order).
• Off-by-one errors in boundary calculations.
• Not handling the case where a region is already homogeneous (leaf node).
• Forgetting to set children pointers for non-leaf nodes.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

construct_quad_tree_space_optimized.py

"""
Solution for Construct Quad Tree
"""

def solve():
    """Implementation for approach 3 of Construct Quad Tree"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

construct_quad_tree_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Construct Quad Tree
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

ConstructQuadTreeSpaceOptimized.java

/**
 * Solution for Construct Quad Tree
 * Approach 3
 */
public class ConstructQuadTreeSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

construct_quad_tree_space_optimized.js

/**
 * Solution for Construct Quad Tree
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

construct_quad_tree_space_optimized.rs

/// Solution for Construct Quad Tree
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

construct_quad_tree_space_optimized.go

package main

import "fmt"

// Solution for Construct Quad Tree
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Convert Sorted Array to Binary Search Tree ↗ Easy #108
• Sort List ↗ Medium #148
• Merge k Sorted Lists ↗ Hard #23

Interview Tips

Key trade-offs to discuss

• Homogeneity check: O(size²) per region; memoization or prefix sums could optimize.
• Recursive vs. iterative: Recursive is cleaner; iterative uses more space but avoids stack overhead.
• Applications: Image compression (store regions of uniform color), spatial indexing, collision detection in games.
• Follow-up: How would you serialize/deserialize the quad tree?
• Edge cases: Single cell (always leaf), all zeros/ones (single leaf), all different values (deep tree).

← Previous
#426 Convert Binary Search Tree to Sorted Doubly Linked List Next
#428 Serialize and Deserialize N-ary Tree →