top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

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

+4 votes
5,315 views

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

posted Oct 25, 2013 by Priyanshi Goyal

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button
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.

1 Answer

0 votes

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)
}
answer Oct 25, 2013 by Salil Agrawal
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++....
Similar Questions
+2 votes

Please share the code or algorithm to delete a node from Threaded Binary Tree.

+2 votes

Given Tree

          6
       /     \
     7        8
   /   \     /  \
  9    10  11    12
                  \
                   13

Expected Output
6 8 12 13

+6 votes

Given binary tree is:

        1
     /     \
    2        3
  /  \        \
 4   5         6
             /   \
            7     8

The output should be 1, 2, 3, 4, 5, 6, 7, 8

...