Construct Quad Tree
Construct Quad Tree is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Preorder Traversal subpattern.
Problem statement
Implement Solution.construct(grid) to build a quad tree representing the binary matrix grid. The matrix has n rows and n columns. A node represents a square region of the matrix and has an isLeaf flag, a val, and up to four children in this order: topLeft, topRight, bottomLeft, and bottomRight.
A node is a leaf exactly when every cell in its region has the same value. Its val must equal that uniform cell value. Otherwise, create an internal node and divide its region into four equal-sized squares, recursively constructing one child for each square in the order listed above.
Return the root Node produced by construct. For an internal node, val may be any value chosen by the solver; the test harness serializes every internal node with val equal to 1. The serialized output uses level order, writing [isLeaf, val] for each node and retaining null child slots needed to preserve positions, while removing trailing null entries.
Example 1:
Input: grid = [[0,1],[1,1]] Output: [[0,1],[1,0],[1,1],[1,1],[1,1]] Explanation: The whole matrix is mixed, so the root is internal. Its four one-cell regions, in top-left, top-right, bottom-left, bottom-right order, contain 0, 1, 1, and 1.
Example 2:
Input: grid = [[0]] Output: [[1,0]] Explanation: The only region contains one cell, so the root is a leaf whose value is 0.
Example 3:
Input: grid = [[1,1,0,0],[1,1,0,0],[0,1,1,1],[1,0,1,1]] Output: [[0,1],[1,1],[1,0],[0,1],[1,1],null,null,null,null,null,null,null,null,[1,0],[1,1],[1,1],[1,0]] Explanation: The root is mixed. Its top-left, top-right, and bottom-right quadrants are uniform leaves with values 1, 0, and 1. The bottom-left quadrant is mixed, so it is an internal node with leaf values 0, 1, 1, and 0; the null entries preserve the level-order child positions of the other leaf nodes.
Constraints:
- grid has n rows and n columns for some n = 2^x. - 0 = 1. - Each recursive region is a square whose side length is a power of two.
Topics and companies
Topics: Array, Matrix, Tree, Recursion, Divide and Conquer.
How to practise Construct Quad Tree on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n^2) time and O(n^2) space.
Open Construct Quad Tree in the code editor, or read the Construct Quad Tree editorial for a worked solution with its approach and complexity analysis.
Where Construct Quad Tree sits in the DSA pattern sheet
- Tree Traversal Patterns (DFS & BFS) pattern guide
- Recursive Preorder Traversal subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Construct Quad Tree
Other problems that use the same Recursive Preorder Traversal and Tree Traversal Patterns (DFS & BFS) techniques:
- Binary Tree Paths — Easy, same subpattern
- Binary Tree Preorder Traversal — Easy, same subpattern
- Construct Binary Tree from Preorder and Inorder Traversal — Medium, same subpattern
- Count Good Nodes in Binary Tree — Medium, same subpattern
- Flatten Binary Tree to Linked List — Medium, same subpattern
- Insert into a Binary Search Tree — Medium, same subpattern