Sorted Linked List to Balanced BST

You have been given a singly linked list in which nodes are present in increasing order. Your task is to construct a Balanced Binary Search Tree with the same data elements as the given Linked List.

A Balanced BST is defined as a BST in which the height of two subtrees of every node differs no more than 1.

Input Format :

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The only line of each test case contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

Output Format :

For each test case, print the nodes of the tree in the level order form separated by single spaces (Print -1 for NULL nodes). Refer to the below example for further clarification.

Print the output for every test case in a separate line.

For Example

Consider the Binary Search Tree-

The above BST will be printed as-
12 10 14 -1 -1 -1 16 -1 -1

Explanation :
Level 1 :
The root node of the tree is 12

Level 2 :
Left child of 12 = 10
Right child of 12 = 14

Level 3 :
Left child of 10 = null(-1)
Right child of 10 = null (-1)
Left child of 14 = null(-1)
Right child of 16 = 16

Level 4 :
Left child of 16 = null (-1)
Right child of 16 = 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 output for each test case ends when all nodes at the last level are null (-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
0 <= N <= 1000
1 <= Data <= 10^9
Data != -1

Time Limit: 1sec