Question

Draw a (single) tree T, such that

• Each internal node of T stores a single character;

• A preorder traversal of T yields: E K D M J G I A C F H B L;

• A postorder traversal of T yields: D J I G A M K F L B H C E.

Part2

Let T be an ordered tree with more than one node. Is it possible that the preorder traversal of T visits the nodes in the same order as the post order traversal of T ? If so, give an example. If not, then explain why this cannot occur.

Answer 1

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// Data structure to store a Binary Tree node
struct Node
{
   int data;
   Node *left, *right;
};

Node* newNode(int key)
{
   Node* node = new Node;
   node->data = key;
   node->left = node->right = nullptr;

   return node;
}

void inorder(Node* root)
{
   if (root == nullptr)
       return;

   inorder(root->left);
   cout << root->data << ' ';
   inorder(root->right);
}

Node* buildTree(auto &preorder, int &pIndex,
               int start, int end, auto &map)
{

   Node* root = newNode(preorder[pIndex]);

   pIndex++;

   if (pIndex == preorder.size())
       return root;

   int index = map[preorder[pIndex]];

   if (start <= index && index + 1 <= end - 1)
   {
     
       root->left = buildTree(preorder, pIndex, start, index, map);

         
       root->right = buildTree(preorder, pIndex, index + 1, end - 1, map);
   }

   return root;
}

Node* buildTree(auto const &preorder, auto const &postorder)
{

   unordered_map<int,int> map;
   for (int i = 0; i < postorder.size(); i++)
       map[postorder[i]] = i;

   int pIndex = 0;

   int start = 0;
   int end = preorder.size() - 1;

     
   return buildTree(preorder, pIndex, start, end, map);
}

int main()
{
   vector<int> preorder = { 1, 2, 4, 5, 3, 6, 8, 9, 7 };
   vector<int> postorder = { 4, 5, 2, 8, 9, 6, 7, 3, 1 };

   Node* root = buildTree(preorder, postorder);

   cout << "Inorder Traversal: ";
   inorder(root);

   return 0;
}