# Build balanced BST from sorted array in C++

In this tutorial, we will learn to how to build a balanced BST(binary search tree) from a sorted array in C++.

We will also see examples to understand the concept in a better way.

## BST from sorted array in C++

The binary search tree is a special type of binary tree which consist of following properties:-

• Left subtree nodes value is lesser than parent node value.
• Right subtree nodes value is greater than the parent node value.
• Each node in left and right subtree also satisfy the above two properties.

Let’s see the diagram,

```                                       6
/   \
BST--->        4      8
/   \   /  \
3      5 7    9```

So,we can see in the above diagram, for each nodes, it’s left subtree nodes value is smaller and right subtree nodes value is greater.

### How to build a balanced BST from a sorted array.

Let,s consider we have a sorted array,

`int arr[]={1,2,3,4,5,6,7};`

So, balanced BST of the given sorted array is,

```                                         4
/     \
BST--->           2           6
/     \     /      \
1        3   5         7```

So, we can see the balanced BST of the given sorted array in the above diagram.

Now, let’s see the pseudocode,

```balancedBST(arr,begin,last)
if begin>start then return.
else do
find the middle element = begin+last/2.
then create a temp node fro middle element.
//then divide the array in left subtree and right subtree
temp->left=balancedBST(arr,begin,middle-1);
temp->right=balancedBST(arr,middle+1,last);
return temp

```

So, let’s see the code implementation.

### C++ Program to build a balanced BST (binary search tree) from a sorted array in C++

```#include<iostream>
#include<bits/stdc++.h>
using namespace std;
//structure declaration
struct Node{
int data;
Node* left;
Node* right;
};
//create function
Node* create(int x){
Node* temp=(Node*)malloc(sizeof(Node));
temp->data=x;
temp->left=NULL;
temp->right=NULL;
}
//function to build balanced BST from a sorted array
Node* buildBalancedBST(int arr[],int begin,int last){
if(begin>last)return NULL;
int middle=(begin+last)/2;
Node* temp=create(arr[middle]);
//divide the array in left subtree and right subtree from middle
temp->left=buildBalancedBST(arr,begin,middle-1);
temp->right=buildBalancedBST(arr,middle+1,last);
return temp;
}
//inorder traversal of balanced BST
void inorder(Node* root){
if(root==NULL)return;
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
//main function
int main(){
int Sortedarr[]={1,2,3,4,5,6,7};
//return a root node
Node* root=buildBalancedBST(Sortedarr,0,6);
cout<<" inorder traveral of the balanced BST is: ";
inorder(root);
}```

Output

`inorder traveral of the balanced BST is: 1 2 3 4 5 6 7`

This is how we can build a balanced BST(binary search tree) from a sorted array in C++.

You may also learn,

Find out the Diameter of the Binary Tree in C++

Build Binary Tree in C++ (Competitive Programming)