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

+4 votes

However it is possible with Binary search tree, please clarify.

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)
}
```

...

5

2 8

1 3 6 9