 ### C++ program to construct binary search tree from given inorder traversal

Description:

1) Find index of the maximum element in array. The maximum element must be root of Binary Tree.
2) Create a new tree node %u2018root%u2019 with the data as the maximum value found in step 1.
3) Call buildTree for elements before the maximum element and make the built tree as left subtree of %u2018root%u2019.
5) Call buildTree for elements after the maximum element and make the built tree as right subtree of %u2018root%u2019.
6) return %u2018root%u2019.

Program:

```#include<stdio.h>
#include<stdlib.h>
#include<iostream>
struct node
{
int data;
struct node* left;
struct node* right;
};

int max(int inorder[], int strt, int end);

struct node* newNode(int data);
struct node* buildTree (int inorder[], int start, int end)
{
if (start > end)
return NULL;

int i = max (inorder, start, end);
struct node *root = newNode(inorder[i]);
if (start == end)
return root;
root->left  = buildTree (inorder, start, i-1);
root->right = buildTree (inorder, i+1, end);

return root;
}
int max (int arr[], int strt, int end)
{
int i, max = arr[strt], maxind = strt;
for(i = strt+1; i <= end; i++)
{
if(arr[i] > max)
{
max = arr[i];
maxind = i;
}
}
return maxind;
}

struct node* newNode (int data)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return node;
}

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

printInorder (node->left);
printf("%d ", node->data);
printInorder (node->right);
}

int main()
{

int inorder[] = {15, 30, 60, 10, 6};
int len = sizeof(inorder)/sizeof(inorder);
struct node *root = buildTree(inorder, 0, len - 1);

printf("\n Inorder traversal of the constructed tree is \n");
printInorder(root);
return 0;
}```

Output:

Inorder traversal of the constructed tree is
15 30 60 10 6 #### More Articles of MAYANK KUMAR:

Name Views Likes
C++ program to remove all leaf nodes from the binary search tree 347 18
C++ program to find K%u2019th largest element in binary search tree when tree modification is not allowed 375 22
C++ program to find K%u2019th smallest element in binary search tree 356 24
C++ program to find second largest element in binary search tree 341 17
C++ program to find K%u2019th largest element in binary search tree 342 19
C++ program to check if each internal node of a binary search tree has exactly one child 319 12
C++ program to reverse a path in binary search tree using queue 347 19
C++ program to check if a binary tree is binary search tree or not 360 15
C++ program to find lowest Common Ancestor in a binary search tree 360 19
C++ program to binary Tree to binary search tree Conversion using std::Set 335 13
C++ program to merge Two binary search trees 367 17
C++ program to construct binary search tree from its given level order traversal 458 29
C++ program to convert a binary search tree to a Binary Tree 416 26
Difference between binary tree and binary search tree 432 26
C++ program to construct binary search tree from given inorder traversal 446 19
C++ program to convert binary tree to binary search tree 566 19
C++ Program to Print String 350 18
C++ Program to List Files in Directory 377 21
C++ Program to Delete Files 283 15
C++ Program to Get IP Address 384 24
C++ Program to Print Date and Time 331 11
C++ Program to Copy Files 338 19
C++ Program to Write to File 319 20
C++ Program to Read a File 322 19
C++ Program to Swap Two Variables 315 15
C++ Program to Find Largest of Two Number 373 20
C++ Program to Print Prime Numbers 364 20
C++ Program to Find Square Root of Number 322 15
C++ Program to Calculate Grade of Student 328 23
C++ Program to Calculate Average of Numbers 348 14
C++ Program to Calculate Average Percentage 298 15
C++ Program to Add Subtract Multiply Divide 324 24
C++ Program to Add Two Numbers 354 16
C++ Program to Get Input from User 310 18
C++ Program to Check Whether a String is Palindrome or Not 283 11
C++ Program to Find LCM 264 11
C++ Program to Convert Decimal to Binary Using Recursion 294 14
C++ Program to Find Factorial of Number Using Recursion 305 17
C++ Program to Find Sum of Natural Numbers Using Recursion 359 29
C++ Program to Find HCF or GCD 317 17
C++ Program to Find ASCII Value of Character 291 18
C++ Program to Find Numbers Divisible by Another Number 437 18
C++ Program to Find the Sum of Natural Numbers 270 17
C++ Program to convert Celsius to Fahrenheit 268 16
C++ Program to Check if a Number is Positive, Negative or 0 315 20
C++ Program to find square root of a number 294 19
C++ program for counting sort Algorithm 281 17
C++ programs for Bucket sort Algorithm 253 14
C++ program for Bubble sort 325 15