427. Construct Quad Tree

MediumTreeArrayDivide and ConquerMatrix
Leetcode Link

Problem Description

This problem involves representing a n x n binary matrix (consisting only of 0's and 1's) using a Quad-Tree data structure. A Quad-Tree is a hierarchical tree where each internal node has exactly four children. Here, every node in the Quad-Tree has two attributes – val and isLeaf. val is true if the node corresponds to a grid of 1's, or false if it corresponds to a grid of 0's. The isLeaf attribute is true if the node is a leaf (doesn't have any children), otherwise it's false.

To construct a Quad-Tree from the given binary matrix, we follow these steps:

  1. If all elements in the current grid section are the same, we create a leaf node with the val set to the corresponding value (either 1 or 0), and isLeaf set to true.
  2. If the current grid section contains both 0's and 1's, we split the grid into four equal parts (top-left, top-right, bottom-left, bottom-right) and recursively repeat this process for each sub-grid.
  3. The recursion continues until the entire matrix is represented as a Quad-Tree.

The goal is to return the root of the Quad-Tree representing the given matrix.

Intuition

To solve this problem, a divide and conquer approach is used, which is well-suited for the Quad-Tree data structure. Here's the intuition behind our solution:

  1. Define a recursive function dfs that accepts the coordinates of the top-left and bottom-right corners of the current grid section as parameters.
  2. Check if the current grid section contains all 0's or all 1's. If all values are the same, we create a leaf node with isLeaf set to true and val reflecting the common value.
  3. If different values are present, the current node is not a leaf (set isLeaf to false). The value of val can be arbitrarily set when isLeaf is false; in our case it is set based on the presence of ones in the section.
  4. Recursively apply step 2 and 3 to the four sub-grids to create the topLeft, topRight, bottomLeft, and bottomRight children of the current node.
  5. Combine the four recursively created child nodes to form the current internal node, and return it.

By applying this intuitive recursive strategy, we process the entire grid, dividing it as necessary, and construct the Quad-Tree from the bottom up.

Learn more about Tree and Divide and Conquer patterns.

Solution Approach

The solution provided in the reference implements a recursive function called dfs which is the essence of the divide and conquer strategy used in constructing the Quad-Tree.

Here's a detailed walk-through of the solution:

  1. Definition of the Recursive Function:

    • The recursive function dfs takes parameters a, b, c, d which define the top-left (a, b) and bottom-right (c, d) corners of the current section of the grid.

  2. Base Case Check for Leaf Nodes:

    • Within the function, two counters, zero and one, are initialized to keep track of the number of zeros and ones in the current grid section.
    • The function then iterates over the grid section, updating zero and one accordingly. After counting, if the sum of zero and one is 1, it means all elements in the section are the same, indicating this is a leaf node.

  3. Creation of Leaf Nodes:

    • If a leaf node is detected (only zeros or only ones are present), isLeaf is set to True. The val is then set to True only if there are ones present, and False otherwise (due to the counting logic). A new Node is created with the val and isLeaf values, and without any children (since it's a leaf).

  4. Splitting the Grid and Recursion:

    • If the section is not uniform (contains both zeros and ones), the function splits the current section into four sub-sections. This is done by dividing the current grid coordinates into four quarters, represented as topLeft, topRight, bottomLeft, and bottomRight.
    • The dfs function is then called recursively on each of the four sub-sections.

  5. Constructing Internal Nodes:

    • After the recursive calls return Node objects for each of the four subsections, a new Node is created to represent the current internal node.
    • The isLeaf is set to False for internal nodes, and val is set based on whether any ones are present in the original section (True if any ones are found, otherwise False).

  6. Return the Quad-Tree Root:

    • Finally, the recursive function is called with the initial full grid sizes, constructing the entire Quad-Tree.
    • The root node of the constructed Quad-Tree, which represents the entire matrix, is returned as the final result.

The algorithms and data structures used in this solution are as follows:

  • Divide and Conquer Algorithm: The Quad-Tree is constructed using a divide and conquer approach, recursively breaking down the matrix into smaller sub-matrices until the base case (uniform section) is reached.
  • Recursion: The construction of Quad-Tree nodes for sub-matrices relies on recursive calls to the same function, a fundamental pattern in divide and conquer algorithms.
  • Custom Data Structures: The Node class provides a blueprint for Quad-Tree nodes, including boolean flags for val and isLeaf, and pointers to child nodes.

The solution makes intelligent use of recursion to handle the complexity of Quad-Tree construction and elegantly handles the condition of leaf and internal nodes within a single function.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a 2 x 2 binary matrix to illustrate the solution approach:

Matrix:
1 0
0 1

Here's the walkthrough using the recursive solution approach:

  1. Initial Call to Recursive Function:

    • We start by calling the dfs function with the full grid size, which in this example is dfs(0, 0, 1, 1), where (0, 0) is the top-left and (1, 1) is the bottom-right corner of the matrix.

  2. Checking for Leaf Nodes:

    • The zero and one counters are initialized. The function then iterates over the entire matrix, i.e., from 0, 0 to 1, 1. It finds that neither zero nor one sum up to 1 alone—both values are present—indicating that this is not a leaf node.

  3. Splitting the Grid:

    • Since the matrix contains both a zero and a one, we split the matrix into four subsections: 
      Top-Left Subsection: 1 (dfs(0, 0, 0, 0))
Top-Right Subsection: 0 (dfs(0, 1, 0, 1))
Bottom-Left Subsection: 0 (dfs(1, 0, 1, 0))
Bottom-Right Subsection: 1 (dfs(1, 1, 1, 1))

  4. Recursive Calls for Subsections:

    • For each subsection, we call the dfs function recursively. Each sub-grid now consists of a single element and is therefore uniform, making each a leaf node.

  5. Creating Leaf Nodes:

    • The dfs function, after being called on a singleton subsection, will create a leaf node with isLeaf set to True and val set to the value of that single element (either True for 1 or False for 0).

  6. Constructing Internal Nodes:

    • We now have four leaf nodes for each of the subsections, as obtained from the recursion: 
      topLeft Node: value = True, isLeaf = True
topRight Node: value = False, isLeaf = True
bottomLeft Node: value = False, isLeaf = True
bottomRight Node: value = True, isLeaf = True
    • These nodes are combined into a new internal Node with isLeaf set to False. Since the original section contained ones, the val for this internal node can be set to True.

  7. Returning the Quad-Tree Root:

    • The internal node created in the previous step is the root node of the Quad-Tree representing our 2 x 2 matrix, and it will be returned by the initial call to the dfs function.

By following these steps, the Quad-Tree for the 2 x 2 matrix is successfully constructed with one internal node (root) and four leaf nodes representing each of the matrix elements.

Solution Implementation

1from typing import List
2
3# Definition for a QuadTree node.
4class Node:
5    def __init__(self, val: bool, is_leaf: bool, top_left=None, top_right=None, bottom_left=None, bottom_right=None):
6        self.val = val
7        self.is_leaf = is_leaf
8        self.top_left = top_left
9        self.top_right = top_right
10        self.bottom_left = bottom_left
11        self.bottom_right = bottom_right
12
13
14class Solution:
15    def construct(self, grid: List[List[int]]) -> Node:
16        # Define a recursive function to traverse the grid and build the QuadTree
17        def dfs(top: int, left: int, bottom: int, right: int) -> Node:
18            # Initialization counters for the zeros and ones in the current grid segment
19            zero_count = one_count = 0
20
21            # Traverse the current segment of the grid to count zeros and ones
22            for i in range(top, bottom + 1):
23                for j in range(left, right + 1):
24                    if grid[i][j] == 0:
25                        zero_count += 1
26                    else:
27                        one_count += 1
28
29            # Determine if the current segment is a leaf (either all zeros or ones)
30            is_leaf = is_leaf = zero_count == 0 or one_count == 0
31            # The value of the leaf is true if there's at least one "1", otherwise false
32            val = is_leaf and one_count == 1
33
34            # If the segment is a leaf, create a leaf node and return it
35            if is_leaf:
36                return Node(grid[top][left], True)
37
38            # Otherwise, recursively divide the grid segment into quadrants and construct subtrees
39            mid_vertical = (top + bottom) // 2
40            mid_horizontal = (left + right) // 2
41            top_left = dfs(top, left, mid_vertical, mid_horizontal)
42            top_right = dfs(top, mid_horizontal + 1, mid_vertical, right)
43            bottom_left = dfs(mid_vertical + 1, left, bottom, mid_horizontal)
44            bottom_right = dfs(mid_vertical + 1, mid_horizontal + 1, bottom, right)
45
46            # Create and return an internal node with the constructed subtrees
47            return Node(val, False, top_left, top_right, bottom_left, bottom_right)
48
49        # Call the recursive function starting with the bounds of the entire grid
50        return dfs(0, 0, len(grid) - 1, len(grid[0]) - 1)
51
52# Example usage:
53# solution = Solution()
54# quad_tree_root = solution.construct([[1, 1], [1, 1]])
55
1class Solution {
2    // Method to construct the quad-tree from a given grid
3    public Node construct(int[][] grid) {
4        // Call the recursive function with the entire grid dimensions
5        return buildTree(0, 0, grid.length - 1, grid[0].length - 1, grid);
6    }
7
8    // Recursive function to build the quad-tree
9    private Node buildTree(int topLeftRow, int topLeftCol, int bottomRightRow, int bottomRightCol, int[][] grid) {
10        int zeroCount = 0, oneCount = 0;
11
12        // Check each element in the current grid section to count zeros and ones
13        for (int row = topLeftRow; row <= bottomRightRow; ++row) {
14            for (int col = topLeftCol; col <= bottomRightCol; ++col) {
15                if (grid[row][col] == 0) {
16                    zeroCount = 1;
17                } else {
18                    oneCount = 1;
19                }
20                // If we found at least one of each, we can break early
21                if (zeroCount + oneCount == 2) {
22                    break;
23                }
24            }
25        }
26
27        // Determine if the current section is a leaf node (has only zeros or only ones)
28        boolean isLeaf = zeroCount == 0 || oneCount == 0;
29        // If it's a leaf node and there was at least one '1', the value is true
30        boolean val = isLeaf && oneCount == 1;
31
32        // Create a new quad-tree node with the calculated value and isLeaf status
33        Node node = new Node(val, isLeaf);
34
35        // If it's not a leaf node, we need to divide the current section into four parts and recurse
36        if (!isLeaf) {
37            int midRow = (topLeftRow + bottomRightRow) / 2;
38            int midCol = (topLeftCol + bottomRightCol) / 2;
39
40            // Define the four children by dividing the current grid section
41            node.topLeft = buildTree(topLeftRow, topLeftCol, midRow, midCol, grid);
42            node.topRight = buildTree(topLeftRow, midCol + 1, midRow, bottomRightCol, grid);
43            node.bottomLeft = buildTree(midRow + 1, topLeftCol, bottomRightRow, midCol, grid);
44            node.bottomRight = buildTree(midRow + 1, midCol + 1, bottomRightRow, bottomRightCol, grid);
45        }
46
47        // Return the constructed quad-tree node
48        return node;
49    }
50}
51
52// Definition for a QuadTree node
53class Node {
54    public boolean val;
55    public boolean isLeaf;
56    public Node topLeft;
57    public Node topRight;
58    public Node bottomLeft;
59    public Node bottomRight;
60
61    public Node() {
62        this.val = false;
63        this.isLeaf = false;
64        this.topLeft = null;
65        this.topRight = null;
66        this.bottomLeft = null;
67        this.bottomRight = null;
68    }
69
70    public Node(boolean val, boolean isLeaf) {
71        this.val = val;
72        this.isLeaf = isLeaf;
73        this.topLeft = null;
74        this.topRight = null;
75        this.bottomLeft = null;
76        this.bottomRight = null;
77    }
78
79    public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
80        this.val = val;
81        this.isLeaf = isLeaf;
82        this.topLeft = topLeft;
83        this.topRight = topRight;
84        this.bottomLeft = bottomLeft;
85        this.bottomRight = bottomRight;
86    }
87}
88
1class Solution {
2public:
3    // Construct a quad tree from a 2D grid
4    Node* construct(vector<vector<int>>& grid) {
5        // Entry point for recursive division of the grid
6        return buildQuadTree(0, 0, grid.size() - 1, grid[0].size() - 1, grid);
7    }
8
9private:
10    // Helper function to recursively divide the grid and build a quad tree
11    Node* buildQuadTree(int topRow, int leftCol, int bottomRow, int rightCol, vector<vector<int>>& grid) {
12        // Counters to check if a cell is homogeneous (all 0s or 1s)
13        int zeroCount = 0, oneCount = 0;
14
15        // Checking each cell in the grid to determine if the current area is homogeneous
16        for (int i = topRow; i <= bottomRow; ++i) {
17            for (int j = leftCol; j <= rightCol; ++j) {
18                if (grid[i][j] == 1)
19                    oneCount = 1;
20                else
21                    zeroCount = 1;
22            }
23        }
24
25        // If only zeros or ones are present, we have a leaf node
26        bool isLeaf = zeroCount == 0 || oneCount == 0;
27        bool val = isLeaf && oneCount; // The value of the leaf node if it's homogeneous
28
29        // Create a new quad tree node with the value and leaf status
30        Node* node = new Node(val, isLeaf);
31
32        // If current area is not homogeneous, divide the area further into quadrants
33        if (!isLeaf) {
34            int midRow = (topRow + bottomRow) / 2;
35            int midCol = (leftCol + rightCol) / 2;
36
37            // Recursively build quad tree for each of the quadrants
38            node->topLeft = buildQuadTree(topRow, leftCol, midRow, midCol, grid);
39            node->topRight = buildQuadTree(topRow, midCol + 1, midRow, rightCol, grid);
40            node->bottomLeft = buildQuadTree(midRow + 1, leftCol, bottomRow, midCol, grid);
41            node->bottomRight = buildQuadTree(midRow + 1, midCol + 1, bottomRow, rightCol, grid);
42        }
43
44        // Return the newly created quad tree node
45        return node;
46    }
47};
48
1// Define the structure for a Node in the quad tree
2interface Node {
3    val: boolean;
4    isLeaf: boolean;
5    topLeft: Node | null;
6    topRight: Node | null;
7    bottomLeft: Node | null;
8    bottomRight: Node | null;
9}
10
11// Function to construct a quad tree from a 2D grid
12function construct(grid: number[][]): Node | null {
13    // Entry point for recursive division of the grid
14    return buildQuadTree(0, 0, grid.length - 1, grid[0].length - 1, grid);
15}
16
17// Helper function to recursively divide the grid and build a quad tree
18function buildQuadTree(topRow: number, leftCol: number, bottomRow: number, rightCol: number, grid: number[][]): Node | null {
19    // Counters to check if a cell is homogeneous (all 0s or 1s)
20    let zeroCount = 0, oneCount = 0;
21
22    // Checking each cell in the grid to determine if the current area is homogeneous
23    for (let i = topRow; i <= bottomRow; ++i) {
24        for (let j = leftCol; j <= rightCol; ++j) {
25            if (grid[i][j] == 1) {
26                oneCount = 1;
27            } else {
28                zeroCount = 1;
29            }
30        }
31    }
32
33    // If only zeros or ones are present, we have a leaf node
34    const isLeaf = zeroCount === 0 || oneCount === 0;
35    // The value of the leaf node if it's homogeneous
36    const val = isLeaf && oneCount === 1;
37
38    // Create a new quad tree node with the value and leaf status
39    const node: Node = {
40        val,
41        isLeaf,
42        topLeft: null,
43        topRight: null,
44        bottomLeft: null,
45        bottomRight: null
46    };
47
48    // If the current area is not homogeneous, divide the area further into quadrants
49    if (!isLeaf) {
50        const midRow = Math.floor((topRow + bottomRow) / 2);
51        const midCol = Math.floor((leftCol + rightCol) / 2);
52
53        // Recursively build quad tree for each of the quadrants
54        node.topLeft = buildQuadTree(topRow, leftCol, midRow, midCol, grid);
55        node.topRight = buildQuadTree(topRow, midCol + 1, midRow, rightCol, grid);
56        node.bottomLeft = buildQuadTree(midRow + 1, leftCol, bottomRow, midCol, grid);
57        node.bottomRight = buildQuadTree(midRow + 1, midCol + 1, bottomRow, rightCol, grid);
58    }
59
60    // Return the newly created quad tree node
61    return node;
62}
63

Time and Space Complexity

The given Python code is a recursive function for constructing a quadtree from a 2D grid. The time and space complexity of this function can be analyzed as follows:

Time Complexity

The time complexity of the code is O(N^2 * logN) where N is the length of rows or columns of the grid. Every recursive call processes a quarter of the current grid size until the base case is hit (when the grid represents a leaf node). The grid is divided until each cell is processed. The leaf checks involve iterating over each cell in the current grid dimension (hence O(N^2)), and this happens logN times due to the division of the grid into quarters at each level of recursion.

Space Complexity

The space complexity is O(logN) which is incurred due to the recursion stack. In the worst-case scenario, our recursion will go as deep as the height of the quadtree, which is logN where N is the number of rows (or columns) in the grid. There is an additional constant space used for zero, one, and isLeaf tracking, and temporary Node creation, but these do not scale with N and thus only add up to O(1) overhead.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which data structure is used to implement priority queue?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

Divide and Conquer Intro

https algomonster s3 us east 2 amazonaws com cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger

LeetCode Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More