top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

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

+5 votes
760 views
How to construct a binary search tree from a given postorder or preorder sequence.
posted Oct 25, 2013 by Luv Kumar

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

0 votes
  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; 
}
answer Oct 25, 2013 by Salil Agrawal
Similar Questions
+4 votes

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

+2 votes

Guys can someone help me by describing the skip-list and why someone should use it over BST.

+2 votes

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

...