PostToPreFullTree.cpp

//Post order to pre order travesal without building tree

//Assume tree is full tree just like min max heap

#include<iostream>

using namespace std;


struct Node
{
   int data;
   Node* left;
   Node* right;
};

int SubTreeSize(int index, int n)
{
     if(index >= n) return 0;

     return 1 + SubTreeSize(2*index + 1,n) +  SubTreeSize(2* index + 2,n);
}
void PostToPre(int arr[],int n, int low, int high, int res[],int i)
{
   if(low > high) return;

   static int index = 0;

   if(low == high)
   {
       res[index++] = arr[low];
       return;
   }

   res[index++] = arr[high];

   int lSize = SubTreeSize(2*i + 1,n);
   int rSize = SubTreeSize(2*i + 2,n);


   PostToPre(arr,n,low,low + lSize-1,res,2*i + 1);
   PostToPre(arr,n,high - rSize,high -1,res,2*i + 2);

}
int main()
{
   int postArr[] = {8,9,4,10,11,5,2,6,7,3,1};

   int n = sizeof(postArr)/sizeof(postArr[0]);

   int* res = new int[n];

   PostToPre(postArr,n,0,n-1,res,0);


   for(int i = 0; i < n; i++)
   {
      cout<<res[i]<<"  ";
   }

   return 0;
}