DSA problem

Construct Quad Tree

MediumDivide and ConquerPattern: Divide and Conquertop300GoogleAmazonMicrosoftBloombergApple

Given an n x n binary matrix grid (where n is a power of two), construct a Quad-Tree that represents it. A Quad-Tree is a tree in which each internal node has exactly four children, conventionally labelled topLeft, topRight, bottomLeft, and bottomRight. Each node stores two booleans: val (the cell value if this node represents a uniform region) and isLeaf (whether the node is a leaf).

The tree is built by recursively partitioning the grid. If a region of the grid is uniform — every cell holds the same value — the region is represented by a single leaf node whose val matches that uniform value. Otherwise the region is split into four equal quadrants, each constructed recursively, and the four results are stitched together under a single non-leaf parent whose val field is arbitrary (commonly set to true on LeetCode but ignored when isLeaf is false).

The natural algorithm is a textbook divide-and-conquer. The recursion takes the bounding box (r1, c1, r2, c2) of the current region. If the region is uniform, return a leaf node. Otherwise, compute the midpoints, recursively build all four quadrants, and combine them into a non-leaf node. The base case (a single cell) is automatically uniform and therefore a leaf.

Checking uniformity by scanning the region costs O(k²) for a side length k, which gives an overall complexity of O(n² log n) — at each of the log n recursion levels we touch every cell once for the uniformity check. This is acceptable for the constraints. A more sophisticated implementation uses a 2D prefix sum to answer uniformity queries in O(1), bringing the total to O(n²). For clarity we present the canonical recursive version, which is the cleanest expression of the divide-and-conquer pattern.

Examples

Constraints

• n == grid.length == grid[i].length
• n == 2^x where 0 <= x <= 6
• grid[i][j] is either 0 or 1.

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

divide-and-conquertreematrixrecursion

Browse all DSA problems