Construct Quad Tree – 427. LeetCode

A Quad Tree is a tree data structure used to partition a 2D space into smaller regions for efficient representation and computation. In this problem, we are given a binary matrix and need to construct a Quad Tree where each node represents a region of the matrix. If all values in the region are the same, the node is a leaf; otherwise, it splits into four subregions.

This problem involves recursive subdivision of the matrix, making it a great example to learn divide-and-conquer techniques.

Optimized Approach: Divide and Conquer

Instead of repeatedly checking all cells in a region, the optimized approach leverages divide-and-conquer:

• Subdivide the grid recursively until base cases are reached.

• Only check the values of subregions instead of re-scanning the grid.

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft, topRight, bottomLeft, bottomRight;

    public Node(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
    }
}

public class ConstructQuadTree {
    public Node construct(int[][] grid) {
        return buildTree(grid, 0, 0, grid.length);
    }

    private Node buildTree(int[][] grid, int row, int col, int size) {
        // Base case: Single cell
        if (size == 1) {
            return new Node(grid[row][col] == 1, true);
        }

        // Divide grid into four quadrants
        int newSize = size / 2;
        Node topLeft = buildTree(grid, row, col, newSize);
        Node topRight = buildTree(grid, row, col + newSize, newSize);
        Node bottomLeft = buildTree(grid, row + newSize, col, newSize);
        Node bottomRight = buildTree(grid, row + newSize, col + newSize, newSize);

        // Check if all quadrants can be merged
        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);
        }

        // Otherwise, create an internal node
        Node root = new Node(false, false);
        root.topLeft = topLeft;
        root.topRight = topRight;
        root.bottomLeft = bottomLeft;
        root.bottomRight = bottomRight;
        return root;
    }
}

Line-By-Line Explanation

Step 1: Build Tree

private Node buildTree(int[][] grid, int row, int col, int size) {

• Handles the recursion and construction logic for dividing the grid into quadrants.

Step 2: Base Case

if (size == 1) {
    return new Node(grid[row][col] == 1, true);
}

• Checks if the region is a single cell
• Creates and returns a leaf node

Step 3: Divide the Grid into Four Quadrants

int newSize = size / 2;
Node topLeft = buildTree(grid, row, col, newSize);
Node topRight = buildTree(grid, row, col + newSize, newSize);
Node bottomLeft = buildTree(grid, row + newSize, col, newSize);
Node bottomRight = buildTree(grid, row + newSize, col + newSize, newSize);

• Divides the current region into four equal quadrants
• Recursively calls buildTree for each quadrant.

Step 4: Check if Quadrants Can Be Merged

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);
}

• Checks if all four quadrants are leaf nodes and have the same value. If true, merge nodes into a single lead node with the common value.
• Merging reduces memory usage and tree depth, improving performance.

Step 6: Create an Internal Node

Node root = new Node(false, false);
root.topLeft = topLeft;
root.topRight = topRight;
root.bottomLeft = bottomLeft;
root.bottomRight = bottomRight;
return root;

• Creates an internal node:
  • val = false: Internal nodes don’t store meaningful values.
  • isLeaf = false: Indicates the node is not a leaf.
• Links the four quadrants as child nodes.

Why This Code Works

This recursive approach efficiently constructs a Quad Tree, following best practices for clarity, modularity, and performance. It leverages the natural hierarchical structure of the problem to ensure correctness and optimality.