Construct Quad Tree

                                            
/**
 * // Definition for a QuadTree node.
 * function Node(val,isLeaf,topLeft,topRight,bottomLeft,bottomRight) {
 */

var construct = function(grid) {
    const isLeaf = (grid, row, col, size) => {
        const val = grid[row][col];
        for (let i = row; i < row + size; i++) {
            for (let j = col; j < col + size; j++) {
                if (grid[i][j] !== val) {
                    return false;
                }
            }
        }
        return true;
    };
    
    const build = (grid, row, col, size) => {
        if (isLeaf(grid, row, col, size)) {
            return new Node(grid[row][col] === 1, true, null, null, null, null);
        } else {
            const half = size / 2;
            return new Node('*', false, build(grid, row, col, half), build(grid, row, col + half, half), build(grid, row + half, col, half), build(grid, row + half, col + half, half));
        }
    };
    
    return build(grid, 0, 0, grid.length);
};

                                            
/**
 * Definition for node.
 * class Node {
 *     val: boolean
 *     isLeaf: boolean
 *     topLeft: Node | null
 *     topRight: Node | null
 *     bottomLeft: Node | null
 *     bottomRight: Node | null
 * }
 */
function construct(grid: number[][]): Node | null {
    function buildTree(row: number, col: number, size: number): Node | null {
        if (size === 1) {
            return new Node(grid[row][col] === 1, true, null, null, null, null);
        }
        
        const topLeft = buildTree(row, col, size / 2);
        const topRight = buildTree(row, col + size / 2, size / 2);
        const bottomLeft = buildTree(row + size / 2, col, size / 2);
        const bottomRight = buildTree(row + size / 2, col + size / 2, size / 2);
        
        if (topLeft?.isLeaf && topRight?.isLeaf && bottomLeft?.isLeaf && bottomRight?.isLeaf &&
            (topLeft.val === topRight.val) && (topRight.val === bottomLeft.val) && (bottomLeft.val === bottomRight.val)) {
            return new Node(topLeft.val, true, null, null, null, null);
        } else {
            return new Node(true, false, topLeft, topRight, bottomLeft, bottomRight);
        }
    }
    
    return buildTree(0, 0, grid.length);
};

                                            
/**
 * Definition for a QuadTree node.
 * type Node struct {
 *     Val bool
 *     IsLeaf bool
 *     TopLeft *Node
 *     TopRight *Node
 *     BottomLeft *Node
 *     BottomRight *Node
 * }
 */
func construct(grid [][]int) *Node {
    if len(grid) == 0 {
        return nil
    }
    isLeaf := true
    val := grid[0][0] == 1
    for i := range grid {
        for j := range grid[i] {
            if grid[i][j] != grid[0][0] {
                isLeaf = false
                break
            }
        }
    }
    if isLeaf {
        return &Node{Val: val, IsLeaf: true}
    }
    return &Node{
        IsLeaf: false,
        Val: false,
        TopLeft: construct(subGrid(grid, 0, 0, len(grid)/2)),
        TopRight: construct(subGrid(grid, 0, len(grid)/2, len(grid)/2)),
        BottomLeft: construct(subGrid(grid, len(grid)/2, 0, len(grid)/2)),
        BottomRight: construct(subGrid(grid, len(grid)/2, len(grid)/2, len(grid)/2)),
    }
}

func subGrid(grid [][]int, row, col, size int) [][]int {
    sub := make([][]int, size)
    for i := 0; i < size; i++ {
        sub[i] = make([]int, size)
        copy(sub[i], grid[row+i][col:col+size])
    }
    return sub
}

                                            
# Definition for a QuadTree node.
# class Node
#     attr_accessor :val, :isLeaf, :topLeft, :topRight, :bottomLeft, :bottomRight

def construct(grid)
    if grid.flatten.uniq.size == 1
        return Node.new(grid[0][0] == 1 ? true : false, true, nil, nil, nil, nil)
    else
        n = grid.length
        node = Node.new(false, false, nil, nil, nil, nil)
        node.topLeft = construct(grid[0...n/2].map{|row| row[0...n/2]})
        node.topRight = construct(grid[0...n/2].map{|row| row[n/2..-1]})
        node.bottomLeft = construct(grid[n/2..-1].map{|row| row[0...n/2]})
        node.bottomRight = construct(grid[n/2..-1].map{|row| row[n/2..-1]})
    end
    return node
end

To solve this coding challenge, we will construct a Quad-Tree from a given \( n \times n \) matrix of 0's and 1's. The process involves recursive partitioning of the grid until we reach uniform sub-grids (either all 0's or all 1's) and building the tree by treating each non-uniform sub-grid as an internal node with four children. Let’s delve deeper into the methodology step-by-step.

# Explanation

Quad-Tree Basics

A Quad-Tree is a specialized tree structure used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. Each node in the tree represents a region of the grid:

Leaf node (terminal node) : A region where all elements are the same (either all 0's or all 1's).
Internal node : A region composed of four sub-regions (explained as nodes themselves).

Node Properties in a Quad-Tree:

val : This is the value the node holds. If the node is a leaf, it represents the region's uniform value (0 or 1). If it's an internal node, this value can be any placeholder as it doesn’t signify the uniform value of a region.
isLeaf : A boolean indicating if the node is a leaf.
topLeft, topRight, bottomLeft, bottomRight : The four children nodes representing the four quadrants of the current region.

Steps to Construct a Quad-Tree:

Check for Uniform Region : See if the current sub-grid has the same value.
Recursive Subdivision : If not uniform, divide the grid into four equal sub-grids and recursively process each sub-grid.
Build Nodes : Construct nodes based on the results from the recursive subdivisions.

Let’s outline the process in a detailed manner with pseudocode:

# Step-by-Step Explanation

Step-by-Step Pseudocode and Explanation

Step 1: Uniform Grid Check

A helper function to determine if a sub-grid is uniform (all elements are the same).

                                            
# Check if the sub-grid is uniform
# grid: the entire grid
# start_row, start_col: starting row and column indices of the sub-grid
# size: size of the sub-grid
function isUniform(grid, start_row, start_col, size):
first_val = grid[start_row][start_col]
for row from start_row to start_row + size:
for col from start_col to start_col + size:
if grid[row][col] != first_val:
return false # not uniform
return true # all values in sub-grid are the same

Step 2: Recursive Build Function

A recursive function to construct the Quad-Tree from the grid.

                                            
# Build the Quad-Tree
# grid: the entire grid
# start_row, start_col: starting row and column indices of the sub-grid
# size: size of the sub-grid
function buildTree(grid, start_row, start_col, size):
if size == 1 or isUniform(grid, start_row, start_col, size):
# Create a leaf node
leaf_value = (grid[start_row][start_col] == 1)
return Node(leaf_value, true, null, null, null, null)
else:
# Size of the sub-grid
half_size = size / 2

# Recursively build each quadrant
topLeft = buildTree(grid, start_row, start_col, half_size)
topRight = buildTree(grid, start_row, start_col + half_size, half_size)
bottomLeft = buildTree(grid, start_row + half_size, start_col, half_size)
bottomRight = buildTree(grid, start_row + half_size, start_col + half_size, half_size)

# Create an internal node
return Node('*', false, topLeft, topRight, bottomLeft, bottomRight)

Step 3: Main Function

The main function that initializes the recursion.

                                            
# Main function to initiate the Quad-Tree construction
function construct(grid):
n = length(grid) # assuming grid is a square matrix
if n == 0:
return null # handle edge case if grid is empty
return buildTree(grid, 0, 0, n)

# Detailed Steps in Pseudocode

Define the
isUniform

function to check if a sub-grid is uniform.
Define the
buildTree

function that performs recursive subdivision and node creation.
In
buildTree

, if the sub-grid is uniform or its size is 1 (single cell), create a leaf node with the corresponding value.
If the sub-grid is not uniform, divide it into four smaller grids and recursively process each, then create an internal node with these four children.
Define the
construct

function to handle the initiation of the Quad-Tree construction using
buildTree

.

This method ensures we recursively partition the grid and construct the tree, correctly forming a Quad-Tree that represents the input grid structure.