Construct Binary Tree from given Parent Array representation

Given an array parent which represents a binary tree such that parent-child relationship is defined by ('PARENT'[i], 'i') which means that parent of i is 'PARENT'[i]. The value of the root node will be i if -1 is present at 'PARENT'[i].

For example:

For the parent array {1, -1, 1}, the tree will be:- 

As, parent of 0 is 'PARENT'[0] i.e. 1.
1 is the root as 'PARENT'[1] = -1.
Parent of 2 is 'PARENT'[2] i.e. 1.

Similarly for the parent array { 1, 2, -1}, the tree will be:-

Your task is to create the Binary tree from the given parent array.

Note:

From the parent array, multiple binary trees may be possible. You have to create a binary tree in such a way that these conditions satisfy:-

If the node has a left child as well as a right child, make sure the left child is smaller than the right child. 

If the node has only one child, make sure it has an only left child. 

For {1, -1, 1}, the accepted tree will be:- 

And for {1, -1}, the accepted tree will be, 

Instead of 

Input format:

The first line of input contains an integer 'T' denoting the number of queries or test cases. 

The first line of every test case contains an integer 'N' denoting the size of the parent array. 

The second line of every test case contains 'N' single space-separated integers, representing the elements of the parent array.

Output format:

For each test case, print the level order of the Binary tree in a separate line. 

For example, the level order output for the tree depicted in the below image would be :

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :

Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null (-1).

Note :

The above format was just to provide clarity on how the output is formed for a given tree. 

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Note:

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

Constraints:

1 <= 'T' <= 100
1 <= 'N' <= 3000

Where 'T' is the number of test cases and 'N' denotes the number of nodes in the tree.

Time limit: 1 sec.