Problem Statement

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Balanced tree : a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example :

`Given A : [1, 2, 3] A height balanced BST :

  2
/   \\

1 3`

Problem Link

Sorted Array To Balanced BST - InterviewBit

Code

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 TreeNode* build(const vector<int> &A,int n,int &head)
 {
     if(n==0)
     return NULL;
     
     TreeNode* lst = build(A,n/2,head);
     
     TreeNode *root = new TreeNode(A[head]);
     
     root->left = lst;
     
     head++;
     
     TreeNode* rst = build(A,n-n/2-1,head);
     
     root->right = rst;
     
     return root;
     
     
 }
TreeNode* Solution::sortedArrayToBST(const vector<int> &A) {
    
    int n = A.size();
    int head = 0;
    return build(A,n,head);
}