Construct Quad Tree

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
4 upvotes
Asked in companies
AmazonUber

Problem statement

You are given a square matrix ‘matrix of size ‘N’ containing 0’s and 1’s only. You have to represent the matrix as a Quad-Tree.

A Quad-Tree is a tree data structure where each node has exactly four children 'topLeft', 'topRight', 'bottomLeft', 'bottomRight', 'bottomLeft'. All nodes have two attributes, 'value': 1 if the node represents a grid of 1's or 0 if the node represents a grid of 0's and 'isLeaf': true if the node is leaf node on the tree or false if the node has the four children.

We can construct a Quad-Tree from a two-dimensional area using the following steps:

If the current grid has the same value (i.e., all 1's or all 0's) set isLeaf to true and set 'value' to the value of the grid and set the four children to null and stop.

If the current grid has different values, set “isLeaf” to false and set value to  -1, and divide the current grid into four sub-grids as shown in the image.

Repeat the above steps for each of the children with the proper sub-grid.

alt text

Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The 1st line of each test case contains one integer 'N', representing the size of the square matrix.

The next 'N' lines contain 'N' integers separated by spaces describing rows of matrix 'matrix' (each element of ‘matrix’ is either 0 or 1).
Output Format 
The output represents the Quad-Tree in a level order manner, with each node represented as a comma-separated value isLeaf, value.

If the value of “isLeaf” or “value” is 1 we represent it as 1, 1, and if the value of “isLeaf” or “value” is 0 we represent it as 0, 0, and if the “value” is -1 we represent it as -1.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
N = 2^y where 0 <= y <= 10
matrix[i][j] = 0 or 1

Time Limit: 1 second
Sample Input 1:
2
2
0 1
1 0
8
1 1 1 1 0 0 1 1
1 1 1 1 0 0 1 1
1 1 1 1 1 1 0 0
1 1 1 1 1 1 0 0
1 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0
Sample Output 1:
0, -1 1, 0 1, 1 1, 1 1, 0 
0, -1 1, 1 0, -1 1, 1 1, 0 1, 0 1, 1 1, 1 1, 0
Explanation For Sample Output 1:
For the first test case:
At level 0: [0, -1].
At level 1: [1, 0], [1, 1], [1,1], [1, 0].

For the second test case:

All values in the grid are not the same. We divide the grid into four sub-grids. The topLeft, bottomLeft, and bottomRight each have the same value.

The topRight has different values so we divide it into 4 sub-grids where each has the same value.

At level 0 : [0, -1].
At level 1 : [1, 1], [0, -1], [0, 1], [1, 1], [1, 0].
At level 2 : [1, 0], [1, 1], [1, 1], [1, 0].
Sample Input 2:
2
2
1 1
1 1
1
0
Sample Output 2:
1, 1
1, 0
Hint

Can you think of some recursive technique to divide the grid into equal parts?

Approaches (1)
Divide and Conquer

The idea here is to divide the grid into four equal parts the topLeft, topRight, bottomLeft, bottomRight. And then construct the Quad-Tree in a recursive manner. All four children of a node determine whether it should be a leaf node or not. 

 

A currentNode is a leaf node only if all of its four children’s topLeft.value, topRight.value, bottomLeft.value, bottomRight.value are equal and topLeft.isLeaf, topRight.leaf, bottomLeft.leaf, bottomRight.leaf are true. Then we set current.value to any of its children’s value and set currentNode.isLeaf to True.

 

Otherwise, set currentNode.value to either 0 or 1 and set currentNode.isLeaf to False, and connect the four children links topLeft, topRight, bottomLeft, bottomRight to currentNode.

 

The algorithm is as follows:

 

  • Create a helper function with parameters matrix, x, y, size, and return type QuadTree, where matrix represents a 2D array, (x, y) represents the starting coordinate of the 2D array, size is the current dimension of the grid, and QuadTree represents the structure of the tree itself.
    • If size == 1 i.e this node is a leaf node since its size is 1.
      • Create a newNode with the value same as matrix[x][y], isLeaf set to true, topLeft link as null, topRight link as null, bottomLeft link as null, bottomRight as null.
    • Create a node currentNode of type QuadTree.
    • Declare four variables topLeft, topRight, bottomLeft, bottomRight.
    • Recurse in all four equal cuts i.e top-left, top-right, bottom-left, bottom -right of dimension size / 2.
      • helper(matrix, x, y, size / 2) and set the value returned by it to topLeft, since the start of the top-left grid is (x, y).
      • helper(matrix, x, y + size / 2, len / 2) and set the value returned by it to topRight, since the start of the top-right grid is (x, y + size / 2).
      • helper(matrix, x + size / 2, y, size / 2) and set the value returned by it to bottomLeft, since the start of the bottom-left grid is (x + size / 2, y + size / 2).
      • helper(matrix, x + size / 2, y + size / 2, size / 2) and set the value returned by it to bottomRight, since the start of the bottom-right grid is (x + size / 2, y + size / 2).
    • If all four children are leaf nodes and all of their values are equal, then it’s a leaf node,
      • Set currentNode.value to topLeft.value.
      • Set currentNode.isLeaf to True.
    • Otherwise,
      • Connect all four children to currentNode.
      • Set currentNode.topLeft to topLeft.
      • Set currentNode.topRight to topRight.
      • Set currentNode.bottomLeft to bottomLeft.
      • Set currentNode.bottomRight to bottomRight.
      • Set currentNode.isLeaf to False.
      • Set currentNode.value to -1.
    • Return the currentNode.
Time Complexity

O(N ^ 2), Where ‘N’ is the size in the given grid.

 

Since we are visiting each cell twice which is of order 2 * N * N. So, the overall time complexity is O(N ^ N).

Space Complexity

O(log(N)), Where ‘N’ is the size in the given grid.

 

Since the maximum recursive call stack is of order log4N. So, the overall space complexity is O(logN).

Code Solution
(100% EXP penalty)
Construct Quad Tree
Full screen
Console