We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Construct Quad Tree

Difficulty: Medium

Problem Description

Given a n * n matrix grid of 0's and 1's only. We want to represent grid with a Quad-Tree. Return the root of the Quad-Tree representing grid. A Quad-Tree is a tree data structure in which each internal node has exactly four children. Each node has two attributes: val (True if the node represents a grid of 1's or False if it represents a grid of 0's) and isLeaf (True if the node is a leaf node or False if it has four children).

Key Insights

  • A Quad-Tree can efficiently represent 2D binary matrices by recursively dividing the grid into four quadrants.
  • If all elements in the current grid are the same, the node becomes a leaf, simplifying tree structure.
  • The recursive division continues until uniformity is achieved or until the smallest grid (1x1) is reached.
  • The representation of the tree follows a specific serialization format that captures the structure of the Quad-Tree.

Space and Time Complexity

Time Complexity: O(n^2) - We potentially examine all elements in the grid during the recursive construction of the Quad-Tree.

Space Complexity: O(log(n)) - The maximum depth of the recursion tree can go up to log(n), where n is the size of the grid.

Solution

The solution involves using a recursive approach to traverse the grid. We check if the entire grid contains the same value. If it does, we create a leaf node. Otherwise, we divide the grid into four quadrants (top-left, top-right, bottom-left, bottom-right) and recursively build Quad-Tree nodes for each quadrant. The final tree nodes are linked accordingly.

Code Solutions

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

def construct(grid):
    def isUniform(x1, y1, x2, y2):
        first_val = grid[x1][y1]
        for i in range(x1, x2):
            for j in range(y1, y2):
                if grid[i][j] != first_val:
                    return False
        return True

    def build(x1, y1, x2, y2):
        if isUniform(x1, y1, x2, y2):
            return Node(val=grid[x1][y1], isLeaf=True)
        
        mid_x = (x1 + x2) // 2
        mid_y = (y1 + y2) // 2
        
        node = Node(val=False, isLeaf=False)
        node.topLeft = build(x1, y1, mid_x, mid_y)
        node.topRight = build(x1, mid_y, mid_x, y2)
        node.bottomLeft = build(mid_x, y1, x2, mid_y)
        node.bottomRight = build(mid_x, mid_y, x2, y2)
        
        return node

    return build(0, 0, len(grid), len(grid))
← Back to All Questions