Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 25 Mar, 2021

Moderate

```
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.
```

```
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).
```

```
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.
```

```
You do not need to print anything. It has already been taken care of. Just implement the given function.
```

```
1 <= T <= 10
N = 2^y where 0 <= y <= 10
matrix[i][j] = 0 or 1
Time Limit: 1 second
```

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
- 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.

- Set
- 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.

- Connect all four children to
- Return the
**currentNode**.

- If

Similar problems

SudoKube

Ninja

Posted: 18 May, 2022

SudoKube

Ninja

Posted: 18 May, 2022

SudoKube

Ninja

Posted: 18 May, 2022

SudoKube

Ninja

Posted: 18 May, 2022

SudoKube

Ninja

Posted: 18 May, 2022

SudoKube

Ninja

Posted: 18 May, 2022

SudoKube

Ninja

Posted: 18 May, 2022

King Placement

Moderate

Posted: 22 May, 2022

Ninja and the experiment

Moderate

Posted: 5 Sep, 2022

Search In A Sorted 2D Matrix

Moderate

Posted: 23 Nov, 2022

Spiral Matrix

Easy

Posted: 24 Nov, 2022