Question

• Tree Reconstruction - Pre+In => Post (C++)

Give you pre-order traversal and in-order traversal, please output post-order traversal.

Input

Two lines. Pre-order traversal and in-order traversal.

Output

Post-order traversal.

Sample Input

GDAFEMHZ

ADEFGHMZ

Sample Output

AEFDHZMG

Answer 1

Program:

Sample output:

Rawcode:

#include<iostream>       //cpp program for post order travaersal by taking inoder and preorder as inputs
using namespace std;
int search(char a[], char var, int n)        //Delceration search() function is used to search the var value in corresponding array
{
    for (int i = 0; i < n; i++)
        if (a[i] == var) //if finds
            return i;   // then it will return its inderx value
}
void Post(char inorder[], char preorder[], int n)       //decleration of post() funtion which takes inorder array and preorder array as inputs and prints post order
{
    int r ;       //initializing r variable which for assigning root element

    r=search(inorder,preorder[0],n) ;       //searching for 1st element of preorder in inorder array and assigns it root varible r because first element in preorder is alway root element for finding left and right sub arrays
    if(r!=0)           //if root not equals to 0 which implies left sub tree is not empty
        Post(inorder,preorder+1,r) ;       //callign post() to print total left sub tree by calling recursively
    if(r!=n-1)       //checks for right sub tree non empty
        Post(inorder+r+1,preorder+r+1,n-r-1) ;   //if non empty then post() function print total right sub tree by calling recursively
     
    cout<<preorder[0]<<" " ;   //printing first element of postorder

}
int main()        //main method
{
    char in_order[] = {'A','D','E','F','G','H','M','Z'};    //decleration Inorder array
    char pre_order[] = {'G','D','A','F','E','M','H','Z'};    //decleration of preorder array
    int n = sizeof(in_order) / sizeof(in_order[0]);       //finds size of array either pre or inorder and assigns to n
    cout<<"INPUT\nPre order is "<<endl;
    for(int i=0;i<n;i++)       //for loop printing preorder elements
    {
       cout<<pre_order[i]<<" ";
   }
    cout<<"\nIn order is "<<endl;
    for(int i=0;i<n;i++)       //for loop printing inorder elements
    {
       cout<<in_order[i]<<" ";
   }
   
    cout << "\nOUTPUT\nPostorder traversal " << endl;
    Post(in_order, pre_order, n);        //calling post() function
    return 0;
}

------------------------------------------

Hope you understand.Upvote me.

Thank you.