# Convert Sorted Array to Binary Search Tree

In this article, we are going to see how to convert a sorted array into a binary search tree? This problem can be featured in coding interview rounds. Submitted by Radib Kar, on January 14, 2019

## Problem statement

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

For this problem, 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:

```Let the sorted array to be:
[-1, 3, 6, 8]
The corresponding balanced BST is:
3
/   \
-1     6
\
8
```

Solution:

The algorithm is simply finding the median in the sorted array and assigning it as a root. Then process the subtrees recursively.

Let the function to build the balanced BST from the sorted array is:

buildBST() which has parameters: sorted array, lower index, higher index

has return type: TreeNode* // returns the root actually

```Function buildBST(sorted array, lower index , higher index)
1.  Base case:
IF lower index>higher index
Return NULL
2.  Declare middle index as (lower index + higher index)/2
3.  root=createnode(array[middle index]);
4.  Create the left subtree recursively
Root->left=buildBST(sorted array, lower index, middle index-1)
5.  Create the right subtree recursively
Root->left=buildBST(sorted array, middle index-1,higher index)
6.  Return root
END FUNCTION
```

In the main function we call,

```    Root=buildBST (sorted array, 0, size of array-1)
```

C++ implementation

```#include <bits/stdc++.h>
using namespace std;

// TreeNode node type
class TreeNode{
public:
int val;           //value
TreeNode *left;    //pointer to left child
TreeNode *right;   //pointer to right child
};

// creating new node
TreeNode* newnode(int data)
{
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = data;
node->left = NULL;
node->right = NULL;
return(node);
}

TreeNode* buildBST(vector<int> nums,int low,int high){
if(low>high)
return NULL;

int mid=(low+high)/2;
TreeNode* root=newnode(nums[mid]); //creates new nodes
root->left=buildBST(nums,low,mid-1);
root->right=buildBST(nums,mid+1,high);

return root;
}

TreeNode* sortedArrayToBST(vector<int>& nums) {
TreeNode* root=buildBST(nums,0,nums.size()-1);
return root;
}

void levelOrder(TreeNode* root) {
cout<<"root: \n";
queue<TreeNode*> q;

if(root==NULL){
cout<<"empty tree\n";
}

int count=1;
TreeNode* temp;
q.push(root);
q.push(NULL);

while(!q.empty()){
temp=q.front();
q.pop();
if(temp==NULL){
if(!q.empty()){
cout<<"\nend of level: "<<count++<<endl;
q.push(NULL);
}
}
else{
cout<<temp->val<<" ";
if(temp->left)
q.push(temp->left);
if(temp->right)
q.push(temp->right);
}
}
cout<<"\nend of level: "<<count<<endl;
}

int main(){
int n,no;

cout<<"enter no of elements\n";
cin>>n;
vector<int> v;

cout<<"enter the sorted array\n";
while(n--){
cin>>no;
v.push_back(no);
}

TreeNode* root=sortedArrayToBST(v);
cout<<"displaying level order traversal\n";
levelOrder(root);

return 0;
}
```

Output

```enter no of elements
4
enter the sorted array
-1 3 6 8
displaying level order traversal
root:
3
end of level: 1
-1 6
end of level: 2
8
end of level: 3
```

Example with explanation

```For simplicity all nodes are represented by its value
Let the sorted array to be:
A=-1, 3, 6, 8

So in the main function it calls:
Root=buildBST( A, 0, 3)
---------------------------------------------------

buildBST( A, 0, 3)
base case isn’t met
mid= 1
root= A[1]=3
3->left=buildBST( A, 0, 0)
3->right= buildBST( A, 2, 3)
Return 3 (node)
---------------------------------------------------

buildBST( A, 0, 0)
base case isn’t met
mid= 0
root= A[0]=-1
-1->left=buildBST(A, 0, -1)
(-1)->right= buildBST(A, 1, 0)
Returns -1(node)
---------------------------------------------------

buildBST( A, 2, 3)
base case isn’t met
mid= 2
root= A[2]=6
6->left=buildBST(A, 2, 1)
(6)->right= buildBST(A, 3, 3)
Returns 6(node)
---------------------------------------------------

buildBST( A, 0, -1)
base case is met
Returns null
---------------------------------------------------

buildBST( A, 1, 0)
base case is met
Returns null
---------------------------------------------------

buildBST( A, 2, 1)
base case is met
Returns null
---------------------------------------------------

buildBST( A, 3, 3)
base case isn’t met
mid= 3
root= A[3]=8
8->left=buildBST(A, 3, 2)
(8)->right= buildBST(A, 4, 3)
Returns 8(node)
---------------------------------------------------

buildBST( A, 3, 2)
base case is met
Returns null
---------------------------------------------------

buildBST( A, 4, 3)
base case is met
Returns null

So,
8->left=NULL
8->right=NULL
6->left=NULL
6->right=8
-1->left=NULL
-1->right=NULL
3->left=-1
3->right=6

So the tree becomes:
3
/    \
-1       6
\
8
```