Question

C++

Build a binary tree using a binary tree class member function from the following array of preorder traversal 3,9,20,15,7 and inorder traversal 9,3,15,20,7. Implement the constructor, destructor and all member functions including print postorder traversal of the binary tree.

Answer 1

PLEASE GIVE IT A THUMBS UP, I SERIOUSLY NEED ONE, IF YOU NEED ANY MODIFICATION THEN LET ME KNOW, I WILL DO IT FOR YOU

#include <bits/stdc++.h>
using namespace std;

class node
{
public:
        int data;
        node *left;
        node *right;
};

/* Prototypes for utility functions */
int search(int arr[], int strt, int end, int value);
node *newNode(int data);

//Construct the tree using PreOrder and Inorder
node *buildTree(int in[], int pre[], int inStrt, int inEnd)
{
        static int preIndex = 0;
        if (inStrt > inEnd)
                return NULL;
        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->data);
        /* 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;
}

/* 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;
        }
        return 0;
}

/* Helper function that allocates a new node with the  
given data and NULL left and right pointers. */
node *newNode(int data)
{
        node *Node = new node();
        Node->data = data;
        Node->left = NULL;
        Node->right = NULL;
        return (Node);
}
/* This funtcion is here just to test buildTree() */
void printPostorder(node *node)
{
        if (node == NULL)
                return;
        printPostorder(node->left);
        printPostorder(node->right);
        cout << node->data << " ";
}

/* Driver code */
int main()
{
        int inorder[] = {9, 3, 15, 20, 7};
        int preorder[] = {3, 9, 20, 15, 7};
        int len = sizeof(inorder) / sizeof(inorder[0]);
        node *root = buildTree(inorder, preorder, 0, len - 1);
        cout << "PostOrder traversal of the constructed tree is \n";
        printPostorder(root);
}