C++ program to construct tree from given inorder and preorder traversals

Article Creation Date : 20-Jun-2021 02:25:12 PM

//Description

/* This C++ article involves construction of a binary tree from given inorder 
and preorder traversal.
By knowing the fact of that the leftmost element in the preorder traversal is the root, as 
preorder traversal follows the order root->left->right. After getting the root, 
search it in the inorder traversal. The elements to the left of that element will
be in the left sub-tree, and the elements to the right to the right sub-tree.
Follow this steps recursively.*/
			
//Given
  Consider the following inorder and preorder traversal
  inorder ={12, 25, 30, 37, 40, 50, 60, 62, 70, 75, 87}
  preorder ={50, 25, 12, 37, 30, 40, 75, 62, 60, 70, 87}

//Algorithm

1) Pick an element from Preorder. Increment a Preorder Index Variable (preIndex in below code) to pick next element in next recursive call.
2) Create a new tree node tNode with the data as picked element.
3) Find the picked element%u2019s index in Inorder. Let the index be inIndex.
4) Call buildTree for elements before inIndex and make the built tree as left subtree of tNode.
5) Call buildTree for elements after inIndex and make the built tree as right subtree of tNode.
6) return tNode.

//Time complexity:o(n^2)

//Program

/* my coding task "C++ program to construct tree from given inorder and preorder traversals" */

#include<iostream>
#include<stdlib.h>
using namespace std;

/* Defines the class of the node which has info, left pointer and right pointer*/
class node
{ public:
  int info;
  node* left;
  node* right;
};

/* this is the Prototypes for utility functions */

int search(int arr[], int strt, int end, int value);
node* newNode(int info);

/* this is a recursive function to construct the binary tree from the inorder traversal and preorder traversal */

node* buildTree(int in[], int pre[], int inStrt, int inEnd)
{  static int preIndex = 0;
   if (inStrt > inEnd)
        return NULL;
  /* Pick current node from Preorder traversal using preIndex and increment preIndex */
       node* tNode = newNode(pre[preIndex++]);

    /* If this node has no children then return */
    if (inStrt == inEnd)
        return tNode;

    /* Else find the index of this node in Inorder traversal */
    
     int inIndex = search(in, inStrt, inEnd, tNode->info);

    /* Using index in Inorder traversal, construct left and right subtress */
    
    tNode->left = buildTree(in, pre, inStrt, inIndex - 1);
    tNode->right = buildTree(in, pre, inIndex + 1, inEnd);

    return tNode;
}

/* UTILITY FUNCTIONS */
/* Function to find index of value in arr[start...end] The function assumes that value is present in in[] */

int search(int arr[], int strt, int end, int value)
{   int i;
    for (i = strt; i <= end; i++)
    {
        if (arr[i] == value)
            return i;
    }
}

/* Helper function that allocates a new node with the given data and NULL left and right pointers. */

node* newNode(int info)
{   
    node* Node = new node();
    Node->info = info;
    Node->left = NULL;
    Node->right = NULL;

    return (Node);
}

/* This funtcion is here just to test buildTree() */

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

    /* first recur on left child */
    printInorder(node->left);

    /* then print the data of node */
    cout<<node->info<<" ";

    /* now recur on right child */
    printInorder(node->right);
}
int main()
{   int in[] = {12, 25, 30, 37, 40, 50, 60, 62, 70, 75, 87};
    int pre[] = {50, 25, 12, 37, 30, 40, 75, 62, 60, 70, 87};
    int len = sizeof(in) / sizeof(in[0]);
    node* root = buildTree(in, pre, 0, len - 1);

    /* Let us test the built tree by printing Insorder traversal */
    cout << "Inorder traversal of the constructed tree is \n";
    printInorder(root);
}

//Output

Inorder traversal of the constructed tree is
12 25 30 37 40 50 60 62 70 75 87
Process returned 0 (0x0)   execution time : 0.174 s
Press any key to continue.
        