Similar Problems
Similar Problems not available
Construct Quad Tree  Leetcode Solution
Companies:
LeetCode: Construct Quad Tree Leetcode Solution
Difficulty: Medium
Construct Quad Tree is a problem on LeetCode that requires you to efficiently create a Quad Tree, a tree data structure that is used to represent an image, grid or any twodimensional data. In this data structure, each node has four children, which are either null or represent a quarter of the parent cell. The problem description is as follows:
Given a n * n matrix grid of 0's and 1's, create a quad tree that represents its black and white pixels.
Return the root of the quad tree.
Note that you cannot use the trivial solution of creating a Quad Tree node for each pixel, as the input size can be as large as 10^9.
To efficiently solve this problem, we need to use a divideandconquer approach. The idea is to recursively divide the matrix into four quadrants, create a Quad Tree node for each quadrant, and assign it to the parent node.
To implement this solution, we need to define a Quad Tree class that has the following properties:
 Value: 0 or 1, depending on the quadrant being represented.
 Children: A list of four Quad Tree nodes that represent the four quadrants of the parent node.
We can use the following algorithm to create the Quad Tree:

Check if all the pixels in the matrix have the same value. If yes, create a Quad Tree node with the same value and return it.

If not, divide the matrix into four quadrants (topleft, topright, bottomleft, and bottomright).

Recursively create Quad Tree nodes for each quadrant using steps #1 to #3.

Create a Quad Tree node for the parent node and assign its children to the Quad Tree nodes created in step #3.

Return the root of the Quad Tree.
Here's the Python code that implements the above algorithm:
class Node:
def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
self.val = val
self.isLeaf = isLeaf
self.topLeft = topLeft
self.topRight = topRight
self.bottomLeft = bottomLeft
self.bottomRight = bottomRight
class Solution:
def construct(self, grid: List[List[int]]) > 'Node':
n = len(grid)
if n == 0:
return None
if n == 1:
return Node(grid[0][0], True, None, None, None, None)
if all(grid[i][j] == grid[0][0] for i in range(n) for j in range(n)):
return Node(grid[0][0], True, None, None, None, None)
m = n // 2
topLeft = self.construct([row[:m] for row in grid[:m]])
topRight = self.construct([row[m:] for row in grid[:m]])
bottomLeft = self.construct([row[:m] for row in grid[m:]])
bottomRight = self.construct([row[m:] for row in grid[m:]])
return Node('*',
False,
topLeft,
topRight,
bottomLeft,
bottomRight)
The code first checks if the matrix has only one pixel or if all pixels have the same value. If yes, it creates a Quad Tree node with the same value and returns it.
Otherwise, the code recursively divides the matrix into four quadrants and creates Quad Tree nodes for each quadrant using the same algorithm, and then assigns them to the parent node. The parent node is then returned.
This algorithm has a time complexity of O(n^2 log n), as we need to recursively divide the matrix into four quadrants until we reach a 1x1 grid. However, we only process each pixel once, so the algorithm has a space complexity of O(n^2).
Construct Quad Tree Solution Code
1