Construct Quad Tree

Given an n x n grid of 0s and 1s, construct a quad tree. Each node represents a subgrid. If all values in the subgrid are the same, it is a leaf node; otherwise, it has four children.

Function signature

func Construct(grid [][]int) *Node

Node definition

type Node struct {
	Val         bool
	IsLeaf      bool
	TopLeft     *Node
	TopRight    *Node
	BottomLeft  *Node
	BottomRight *Node
}

Inputs / outputs

• grid: square matrix of 0/1 values.
• Return: root of the quad tree.

Example

Grid:
1 1
1 1

Output: leaf node with Val=true

Constraints

• n is a power of 2
• 1 <= n <= 64

Core idea (near-solution)

Use divide and conquer. If a region is uniform, create a leaf node. Otherwise split into 4 quadrants and recurse.

Invariant: each node represents exactly one subgrid.

Algorithm (step-by-step)

1. Check if the current subgrid is uniform (all 0s or all 1s).
2. If uniform, return a leaf node with Val set accordingly.
3. Otherwise split into 4 equal quadrants and recursively construct children.
4. Return a non-leaf node with those children.

Correctness sketch

• Invariant: each node represents exactly one subgrid.
• The problem is split into independent subproblems.
• By induction, recursive solutions are correct.
• The combine step preserves correctness for the full problem.

Trace (hand walkthrough)

Example input:
Grid:
1 1
1 1

Output: leaf node with Val=true

Walk:
- grid is all 1s -> uniform
- return leaf node with Val=true

Pitfalls to avoid

• Misidentifying a uniform region (must scan the entire subgrid).
• Incorrect quadrant boundaries (off-by-one splits).
• Using Val incorrectly for non-leaf nodes (value is irrelevant when IsLeaf is false).

Complexity

• Time: O(n^2) to scan all cells.
• Extra space: O(log n) recursion depth.

Implementation notes (Go)

• Pass (r0, c0, size) indices instead of slicing to avoid allocations.
• Early-exit the uniformity scan once a mismatch is found.