Construct Quad Tree
Given a n × n binary grid where each value is either 0 or 1, construct a Quad Tree representing the grid.
Each Quad Tree node contains:
- val — the value represented by the region.
- isLeaf — whether the node represents a single uniform region.
- topLeft
- topRight
- bottomLeft
- bottomRight
If all values in a region are the same, create a leaf node for that region.
Otherwise, divide the region into four equal-sized parts and recursively construct the four children.
Return the root of the constructed Quad Tree.
Example 1
Input
n = 2 grid = 0 1 1 0
Output
0 0 0 1 1 1 1 1 0 1
Explanation
The complete 2 × 2 grid is not uniform, so it becomes an internal node.
Its four 1 × 1 regions are:
- Top-left → 0
- Top-right → 1
- Bottom-left → 1
- Bottom-right → 0
Each of these is a leaf node.
Example 2
Input
n = 2 grid = 1 1 1 1
Output
1 1
Explanation
All cells contain 1, so the entire grid is represented by a single leaf node.
Constraints
Hints:
Hint 1
First check whether every cell in the current region has the same value.
Hint 2
f the region is not uniform, divide it into four equal parts:
- Top-left
- Top-right
- Bottom-left
- Bottom-right
Author & Technical Reviewer
Technically reviewed by: ExamAdda Technical Review Team
Technical Reviewers, ExamAdda
Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.
Published
Aug 22, 2026
Last updated
Aug 22, 2026
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output