Sorted Array to Balanced BST

PROBLEM :

Given a sorted array. Write a program that creates a Balanced Binary Search Tree using array elements. If there are n elements in array, then floor(n/2)'th element should be chosen as root and same should be followed recursively.

Input:  Array {1, 2, 3}
Output: A Balanced BST
     2
   /  \
  1    3

Input: Array {1, 2, 3, 4}
Output: A Balanced BST
      3
    /  \
   2    4
 /
1

Input:

The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is N,N is the size of array.
The second line of each test case contains N input A[].

Output:

Print the preorder traversal of constructed BST.

Constraints:

1 = T = 100
1 = N = 1000
1 = A[] = 10000

Example:

Input:
1
7
7 6 5 4 3 2 1

Output:
4 6 7 5 2 3 1

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;
struct TREE
{
    int data ;
    struct TREE *left ;
    struct TREE *right ;
};

void preorder(struct TREE *) ;
struct TREE* convert_BST_array(int [],int ,int ) ;

int main()
 {
int t,no,a[1000],i ;
struct TREE *root ;
cin>>t ;
while(t--)
{
   cin>>no ;
   for(i=0;i<no;i++)
   cin>>a[i] ;
 
   root=convert_BST_array(a,0,no-1) ;
   preorder(root) ;
   cout<<endl ;
}

return 0;
}

struct TREE* convert_BST_array(int a[],int start,int end)
{
    if(start>end)
        return NULL;
       
    int mid ;
    mid=(start+end)/2 ;
    struct TREE *root ;
   
    root=(struct TREE*)malloc(sizeof(struct TREE)) ;
    root->data=a[mid] ;
    root->left=convert_BST_array(a,start,mid-1) ;
    root->right=convert_BST_array(a,mid+1,end) ;
   
    return root ;
}

void preorder(struct TREE* root)
{
    if(root==NULL)
    return ;
    cout<<root->data<<" " ;
    preorder(root->left) ;
    preorder(root->right) ;
}

---------------------------------------------------------------------------------