#include <iostream.h>
#include <conio.h>

//For the required binary tree implementation, two traversals of the tree are required; 
//Pre Order Traversal and In Order Traversal

// TreeNode class to create a new node as well as set and get values from it.
class TreeNode
{
 public:
 //constructor
  
  TreeNode(int value)
    {
       this->value = value;
       this->left = NULL;
       this->right = NULL;
   }
//get and set value of the node
  int getInfo()
   {
     return this->value;
   }
  void setInfo(int value)
   {
     this->value = value;
   }
//left child   
  TreeNode* getLeft()
   {
     return left;
   }
  void setLeft(TreeNode* left)
   {
     this->left = left;
   }
//right child   
  TreeNode* getRight()
   {
     return right;
   }
void setRight(TreeNode* right)
{
this->right = right;
}
//Private data memebers include value of a node, left and right child
 private:
  int value;
  TreeNode* left;
  TreeNode* right;
};  //End of class TreeNode


//findposition(...) function is used to find the index of a node value in inorder traversal array.
 
 int findPosition(int* arr, int val, int arrsize)
  {
    for(int i=0; i<arrsize;i++) 
      {
        if(arr[i] == val) 
            return i;
      }
    return -1;
  }

//createBTree function is used to creat Binary Tree from its preorder and inorder traversals. 

 TreeNode* createBTree(int* preorder, int* inorder, int arrsize)
   {
    if(arrsize == 0) return NULL;
 
    int nodeVal = *preorder;      
    TreeNode* node  = new TreeNode(nodeVal);    //first node of the preorder will be the root
    int newPos = findPosition(inorder, nodeVal, arrsize); //its index is find in inorder array
    node->setLeft(createBTree(preorder+1, inorder, newPos)); 
    node->setRight(createBTree(preorder+newPos+1, inorder+newPos+1, arrsize-newPos-1));
    return node;            
   }



// postorder(0) function is used to print postorder traversal of the binary tree created
 
 void postorder(TreeNode* troot)
 {
  if( troot != NULL)
    {
      postorder(troot->getLeft());
      postorder(troot->getRight());
      cout << troot->getInfo()<<" ";
    }

 }  
//below is the main() function
 
int main()
  {
    int preorderarr[] = {18,95,41,29,52,74,86,33,57,17,20}; //array to store preorder traversal of the tree
    int inorderarr[] = {41,95,74,52,29,18,86,57,17,33,20};  //array to store inorder traversal of the tree
 
    TreeNode* btree = createBTree(preorderarr, inorderarr, 11);//tree creat  
    
    cout<<"***** Post order traversal of the given Tree ******" <<endl <<endl;
    postorder(btree); // function call to print postorder traversal of the binary tree created
    
    getche();
    return 0;
  }