C++ program to construct Binary tree from given inorder traversal














































C++ program to construct Binary tree from given inorder traversal



DESCRIPTION:

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.

In this program we have created a binary search tree using vectors.Vectors are same as dynamic arrays with the ability to resize itself
automatically when an element is inserted or deleted, with their storage
being handled automatically by the container.
push_back() : inserts the value at last of vector
begin():Returns an iterator pointing to the first element in the vector
end():Returns an iterator pointing to the theoretical element that follows the last element in the vector
sort(v.begin,v.end()):sort vector elements in ascending order

Algorithm:
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.

EXAMPLE:

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


CODE:

#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