Convert Sorted Array to Balanced BST and Inorder Traversal

You are given a sorted array of integers. Your task is to convert this array into a height-balanced binary search tree (BST) and then perform an in-order traversal of the BST.

A height-balanced BST is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than 1. The in-order traversal of a BST returns the elements in non-decreasing order. Hence, the output of the in-order traversal should be the same as the original sorted array.

The tree is constructed recursively by selecting the middle element as the root, then doing the same for the left subarray for the left subtree and the right subarray for the right subtree.

Algorithm Overview:

• Find the middle element of the array: mid = \( \lfloor\frac{n}{2}\rfloor \).
• Create a node with the middle element as the value.
• Recursively apply the procedure to the subarray left of the middle element and assign it to the left subtree, and do the same for the right subarray and right subtree.
• Perform an in-order traversal (i.e., left-root-right) on the BST to retrieve the elements.

The final result should be printed with each test case's in-order output on a separate line.

inputFormat

The first line of the input contains an integer \( t \) (\( t \ge 3 \)) representing the number of test cases. For each test case:

1. The first integer \( n \) represents the number of elements in the sorted array.
2. Then \( n \) space-separated integers follow, representing the sorted array.

All input is provided via standard input (stdin).

outputFormat

For each test case, output a single line containing the in-order traversal of the BST. The values must be separated by a single space. Output is via standard output (stdout).

## sample

3
5 -10 -3 0 5 9
7 1 2 3 4 5 6 7
1 42

-10 -3 0 5 9
1 2 3 4 5 6 7
42

</p>