How to get preorder sequence from a post order sequence in a binary tree?

Question

For ex : Given post order sequence 1 3 2 6 9 8 5
its pre order sequence is 5 2 1 3 8 6 9

Comments

Tree is, right
                          5
                   2              8
                1    3        6   9

---

I dont think if it is possible if you had given only one sequence. To construct the Binary Tree you require at least two sequence.
However it is possible with Binary search tree, please clarify.

---

To create binary tree we need to find out root only.
In pre order root is on first place.
and post order root is on last place.
So we can create tree form post order OR pre order.
But In case of inorder we can not find root So can not create tree

---

But that can be done with Binary Search Tree, i.e. last node 5 is the root, rightmost of all less then 5 would be root of left subtree while rightmost of all greater would be root of right subtree and so on this algo is possible only with binary search tree not with Binary.

Answer 1

Step 1: Construct the tree.
Step 2: Run the preorder function.

1) Done some cheating (picked from http://tech.queryhome.com/18324/construct-binary-search-given-postorder-preorder-sequence )

CreateTree_from_postorder(a[], length) 
{
   if length <= 0 then return null;

   create a node n;
   n->data = a[length -1];

   lowerElements = getLowerElements(a, length, n->data, &lowerLength);
   higherElements = getHigherElements(a, length, n->data, &higherLength);

   if (lowerLength > 0)
       n->left = CreateTree_from_postorder(lowerElements, lowerLength);
   else 
       n->left = null;

   if (higherLength > 0)
        n->right = CreateTree_from_postorder(higherElements, higherLength);
   else 
       n->right = null;

   return n;
}

getLowerElements(a[], length, pivot, *lowerLength);
{
   int temp[], j=0;
   for (i=0; i<length; i++)
   { 
      if (a[i] < pivot)
         temp[j++] = a[i];
   }
   *lowerLength = j;
   return temp; 
}

getHigherElements(a[], length, pivot, *higherLength);
{
   int temp[],  j=0;
   for (i=0; i<length; i++)
   { 
      if (a[i] > pivot)
         temp[j++] = a[i];
   }
   *higherLength = j;
   return temp; 
}

2) Now run the preorder for created tree

preorder(node)
{
  if node == null then return
  print(node->data)
  preorder(node->left) 
  preorder(node->right)
}

Comments

Temp is local array .
I think we need to make it static.

---

My bad, but its a pseudo code so can escape from liability (ha ha ha) and pass it to the coder who is going to use C/C++....