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

380 views
How to construct a binary search tree from a given postorder or preorder sequence.
posted Oct 25, 2013

If it is preorder then the first node becomes root node ....followed by the left side as left subtree and right side the right subtree.....
If it is in post order then the last node becomes the root node followed by left side of the node is left subtree and right side of the node is right subtree

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