Binary Search Tree is a node-based binary tree data structure which has the following properties:
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:
Comments