Factorial Trailing zeros

427.Construct Quad Tree

Tree

Divide and Conquer

Matrix

Recursion

Problem Statement:

Given a n * n matrix grid of 0's and 1's, construct a Quad-Tree representation of the grid. Each node can be a leaf node with a boolean value or an internal node with four children representing four quadrants.

Example:

Input:

grid = [[1,1],[1,1]]

→

Output:

[[1,1]]

Returns a leaf node since all values are 1

Algorithm:

1. Recursively divide grid into four quadrants
2. Check if quadrant is uniform (all same value)
3. Create leaf node if uniform
4. Create internal node with four children if not uniform

Complexity:

Time: O(n²) | Space: O(log n) for recursion stack

Java Solution:

public Node construct(int[][] grid) {
    // Start recursion with full grid
    return construct(grid, 0, grid.length - 1, 0, grid[0].length - 1);
}

private Node construct(int[][] grid, int x1, int x2, int y1, int y2) {
    // Base case: single cell
    if (x1 == x2) {
        boolean val = grid[x1][y1] == 1;
        return new Node(val, true, null, null, null, null);
    }

    // Find midpoints for quadrants
    int rowMid = (x1 + x2) / 2;
    int colMid = (y1 + y2) / 2;
    
    // Recursively construct four quadrants
    Node topleft = construct(grid, x1, rowMid, y1, colMid);
    Node topright = construct(grid, x1, rowMid, colMid + 1, y2);
    Node bottomleft = construct(grid, rowMid + 1, x2, y1, colMid);
    Node bottomright = construct(grid, rowMid + 1, x2, colMid + 1, y2);

    // Check if all children are uniform leaves with same value
    if (topleft.isLeaf && topright.isLeaf && bottomleft.isLeaf && 
        bottomright.isLeaf && topright.val == topleft.val && 
        topright.val == bottomleft.val && topright.val == bottomright.val) {
        return new Node(topleft.val, true, null, null, null, null);
    }
    
    // Create internal node if not uniform
    return new Node(false, false, topleft, topright, bottomleft, bottomright);
}

Python Solution:

def construct(self, grid: List[List[int]]) -> 'Node':
    def helper(x1: int, x2: int, y1: int, y2: int) -> 'Node':
        # Base case: single cell
        if x1 == x2:
            val = grid[x1][y1] == 1
            return Node(val, True)
            
        # Find midpoints for quadrants
        row_mid = (x1 + x2) // 2
        col_mid = (y1 + y2) // 2
        
        # Recursively construct four quadrants
        topleft = helper(x1, row_mid, y1, col_mid)
        topright = helper(x1, row_mid, col_mid + 1, y2)
        bottomleft = helper(row_mid + 1, x2, y1, col_mid)
        bottomright = helper(row_mid + 1, x2, col_mid + 1, y2)
        
        # Check if all children are uniform leaves with same value
        if (topleft.isLeaf and topright.isLeaf and
            bottomleft.isLeaf and bottomright.isLeaf and
            topleft.val == topright.val == bottomleft.val == bottomright.val):
            return Node(topleft.val, True)
            
        # Create internal node if not uniform
        node = Node(True, False)
        node.topLeft = topleft
        node.topRight = topright
        node.bottomLeft = bottomleft
        node.bottomRight = bottomright
        return node
        
    return helper(0, len(grid) - 1, 0, len(grid[0]) - 1)

C++ Solution:

Node* construct(vectorint>>& grid) {
    return construct(grid, 0, grid.size() - 1, 0, grid[0].size() - 1);
}

Node* construct(vectorint>>& grid, int x1, int x2, 
                      int y1, int y2) {
    // Base case: single cell
    if (x1 == x2) {
        bool val = grid[x1][y1] == 1;
        return new Node(val, true);
    }
    
    // Find midpoints for quadrants
    int rowMid = (x1 + x2) / 2;
    int colMid = (y1 + y2) / 2;
    
    // Recursively construct four quadrants
    Node* topleft = construct(grid, x1, rowMid, y1, colMid);
    Node* topright = construct(grid, x1, rowMid, colMid + 1, y2);
    Node* bottomleft = construct(grid, rowMid + 1, x2, y1, colMid);
    Node* bottomright = construct(grid, rowMid + 1, x2, colMid + 1, y2);
    
    // Check if all children are uniform leaves with same value
    if (topleft->isLeaf && topright->isLeaf && 
        bottomleft->isLeaf && bottomright->isLeaf && 
        topleft->val == topright->val && 
        topleft->val == bottomleft->val && 
        topleft->val == bottomright->val) {
        return new Node(topleft->val, true);
    }
    
    // Create internal node if not uniform
    Node* node = new Node(false, false);
    node->topLeft = topleft;
    node->topRight = topright;
    node->bottomLeft = bottomleft;
    node->bottomRight = bottomright;
    return node;
}