Sorted Array to Balanced BST and Preorder Traversal

Given a sorted array of integers, your task is to convert it into a height-balanced Binary Search Tree (BST) and then output its pre-order traversal. A BST is said to be height-balanced if for every node in the tree, the difference between the heights of its left and right subtrees is at most one, i.e., if the heights are \(h_1\) and \(h_2\), then \(|h_1 - h_2| \le 1\).

You must build the BST by always choosing the middle element of the current subarray as the root. After constructing the tree, perform a pre-order traversal (visit the root, then the left subtree, and finally the right subtree) and output the node values separated by a single space.

inputFormat

The first line contains an integer N, representing the number of elements in the sorted array. The second line contains N space-separated integers in ascending order. For an empty array, N will be 0.

outputFormat

Output a single line containing the pre-order traversal of the constructed BST, with each value separated by a space. If the tree is empty, output an empty line.

7
1 2 3 4 5 6 7

4 2 1 3 6 5 7