BST Problem

You are given the post order traversal,P, of a BST on n elements 1,2,...,n.You have to determine the unique BST tht hasP as its POST ORDER TRAVERSAL.what is the time complexity of the most effecient algorithm for doing this.

n logn for sorting and getting the in order
another logn for making the tree itself from in order and postorder

u can make the BST with the use of only postorder also.....
there is another answer......

bhai ab answer to bata do ..,..kafi time ho gaya post ko..

Step 1. The last node in the post order listing will be the root.

Step 2. Now start from the beginning to the point where the values are less than root.

Step 3. In this new list, the last element will be immediate left child of root.

Step 4. Continue with the new list thus formed.

Step 5. If ( value < root) then left child
................else right child

Step 6. In this way you will build your left subtree of the BST in question.

Repeat this procedure for the Right subtree of the BST. complexity O(nlogn)