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)