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














































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[0]);
    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

Comments