Quite elaborate but easy to understand code. Firstly create empty balanced BST using number of elements required by level order traversal


#1
TreeNode* node(){
     // helper function to get an empty node
     TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
     temp->left=NULL;
     temp->right= NULL;
     return temp;
 }
TreeNode * createtree(int n){
    //Create an empty balanced BST with given number of nodes by level order traversal s.t
    //level balanced is maintained
    TreeNode * head = node();
    queue<TreeNode*> q;
    n--;
    q.push(head);
    while(1){
        TreeNode * temp = q.front();
        q.pop();
        if(n){
            TreeNode * lefty = node();
            temp->left = lefty;
            n--;
            q.push(lefty);
        }
        else break;
        if(n){
            TreeNode * righty = node();
            temp->right = righty;
            n--;
            q.push(righty);
        }
        else break;
    }
    return head;
}
void populate(TreeNode * root, const vector<int > &v, int * i){
    //Inorder traversal and populating empty balanced BST
    if(!root)
        return;
    populate(root->left, v,i);
    root->val = v[*i];
    *i = *i +1;
    populate(root->right, v, i);
}
TreeNode* Solution::sortedArrayToBST(const vector<int> &A) {
    //Driver function
    int n= A.size();
    int i=0;
    TreeNode* root = createtree(n);
    populate(root, A, &i);
    return root;
}