427. Construct Quad Tree

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.

Example Walkthrough

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

1Matrix: 
21 0
30 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:

     1Top-Left Subsection: 1 (dfs(0, 0, 0, 0))
     2Top-Right Subsection: 0 (dfs(0, 1, 0, 1))
     3Bottom-Left Subsection: 0 (dfs(1, 0, 1, 0))
     4Bottom-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:

     1topLeft Node: value = True, isLeaf = True
     2topRight Node: value = False, isLeaf = True
     3bottomLeft Node: value = False, isLeaf = True
     4bottomRight 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

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.