How to construct a binary search tree from a given postorder or preorder sequence.

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

Answer 1

1. If you are given an array with postorder then last element is root.
2. All elements less then last element are part of leftsubtree.
3. All elements more then last element are part of right subtree.

Similarly for the preorder...

Pseudo Code

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; 
}