Binary Search Tree is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node%u2019s key.
• The right subtree of a node contains only nodes with keys greater than the node%u2019s key.
• The left and right subtree each must also be a binary search tree.

1)Get the Middle of the array and make it root.
2) Recursively do same for left half and right half.
      a) Get the middle of left half and make it left child of the root
          created in step 1.
      b) Get the middle of right half and make it right child of the
          root created in step 1.

Input: 4 5 3 8 7 2 9

Inorder Traversal of Binary tree
      8   
    /  \   
   5     2 
 /     /  \
4    3 7   9

Output: 2 3 4 5 7 8 9 

Inorder Traversal of Binary search tree is the sorted inorder traversal of binary tree

      5   
    /   \  
   3     8 
 /     /  \
2    4 7   9

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct node				//format of node's  
{ 
	int data; 
	struct node* left; 
	struct node* right; 
}; 

struct node* newNode (int data) 		//allocating memory for the new node
{ 
	struct node* node = (struct node*)malloc(sizeof(struct node)); 
	node->data = data; 
	node->left = NULL; 
	node->right = NULL; 

	return node; 
}


/*function to create tree from the inorder traversal*/
struct node* buildTree(vector<int>& arr, int start, int end) 
{ 
    if (start > end) 
      return NULL; 
  
    /* Get the middle element and make it root */
    int mid = (start + end)/2; 
    struct node *root = newNode(arr[mid]); 
  
    /* Recursively construct the left subtree */
    root->left =  buildTree(arr, start, mid-1); 
  
    /* Recursively construct the right subtree */
    root->right = buildTree(arr, mid+1, end); 
  
    return root; 
} 

void printInorder (struct node* node) 
{ 
	if (node == NULL) 
		return; 

	printInorder (node->left);		//recurring the left node 
	cout<<node->data<<" "; 		//print the node when no left node is left
	printInorder (node->right);             //recurring the right node
} 

int main() 
{ 
	vector<int> arr;    //creating an vector of integer type	
	int n,k;
	cout<<"Enter the no. of nodes"<<endl;
        cin>>n;
	cout<<"\nEnter the inorder traversal"<<endl;
	for(int i=0;i<n;i++)
	{
	cin>>k;
	arr.push_back(k);        //inserting vector elements
	}
	sort(arr.begin(),arr.end());
	struct node *root = buildTree(arr, 0,arr.size()-1); 
	
	cout<<"\nInorder traversal of the constructed tree is \n"; 
	printInorder(root); 
	cout<<endl;
	return 0; 
} 

OUTPUT: