Balanced Binary Search Tree Construction

You are given a list of integers which may be unsorted. Your task is to construct a balanced Binary Search Tree (BST) from the given list. A balanced BST is such that for every node, the height difference between its left and right subtrees is at most 1. The BST must be built by first sorting the array and then recursively choosing the middle element as the root. The final output should be the inorder traversal of the BST, which will produce the sorted sequence of the input numbers.

Formally, if (A = [a_1, a_2, \dots, a_n]) is the sorted array, the balanced BST is constructed recursively by selecting (a_{\lfloor n/2 \rfloor + 1}) as the root. The left child is constructed from ( [a_1, \dots, a_{\lfloor n/2 \rfloor}] ) and the right child from ( [a_{\lfloor n/2 \rfloor + 2}, \dots, a_n] ).

inputFormat

Input is read from standard input (stdin) and consists of a single line containing space-separated integers. These integers represent the elements which need to be inserted into the BST.

outputFormat

Output should be written to standard output (stdout) and should consist of the inorder traversal of the balanced BST. The numbers must be printed in a single line separated by a single space.## sample

3 1 2

1 2 3