- If you are given an array with postorder then last element is root.
- All elements less then last element are part of leftsubtree.
- 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;
}