Sorted Doubly Linked List to Balanced BST

The first and only line of input contains the node data for the sorted doubly linked list, separated by single spaces. The input is terminated by -1.

Print the level-order traversal of the constructed BST. Each level of the tree should be on a new line, with node values on the same level separated by spaces. A null child should not be printed.

Sample Input 1:

1 2 3 4 5 6 7 -1

Sample Output 1:

4 
2 6 
1 3 5 7

Explanation for Sample 1:

The middle of [1,2,3,4,5,6,7] is 4. 4 becomes the root.
The left half [1,2,3] is used to build the left subtree. Its middle is 2.
The right half [5,6,7] is used to build the right subtree. Its middle is 6.
This process continues recursively, resulting in a balanced BST.

Sample Input 2:

10 20 30 40 50 60 -1

Sample Output 2:

30 
20 50 
10 40 60

Explanation for Sample 2:

The list has an even number of elements. The first of the two middle elements, 30, is chosen as the root.
Left half: [10, 20]. Middle is 10. 20 becomes its right child.
Right half: [40, 50, 60]. Middle is 50. 40 is its left child, 60 is its right.
The resulting tree is height-balanced.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

0 <= Number of nodes <= 1000
-1000 <= Node Value <= 1000
The input list is guaranteed to be sorted.

Time limit: 1 sec