Sorted Linked List to Balanced BST Problem Statement

Given a singly linked list where nodes contain values in increasing order, your task is to convert it into a Balanced Binary Search Tree (BST) using the same data values.

A Balanced BST is defined as a tree where the height of the two subtrees of any node differ by no more than 1.

Input:

The first line of input contains an integer T denoting the number of test cases. Each test case is represented by a single line containing the elements of the linked list, separated by spaces and ending with -1. The value -1 is not a part of the list elements.

Output:

For each test case, output the values of the BST nodes in level order traversal, separated by spaces. Use -1 to represent NULL nodes where applicable. Ensure each test case's output is on a new line.

Example:

Consider the following Binary Search Tree representation:

Output for the above BST will be: 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: Null children (-1) for all except 14, which has a right child 16

Level 4: Null children (-1) for node 16

During output representation, after printing each level's nodes, -1 should be used for non-existing (NULL) children, and the process continues until the last level where all nodes are null (-1).

Constraints:

• 1 ≤ T ≤ 100
• 0 ≤ N ≤ 1000
• 1 ≤ Data ≤ 10^9
• Data never equals -1
• Time Limit: 1 sec