I am unable to find a test case where this particular approach fails( I hardly thinks it's correct but anyway here it is).
We make the last element the root of the BST. And keep inserting each element one by one just like normal binary tree insertion. This will take O(n^2) time in worst case( when the tree is only leftist or rightist). For a balance tree it will be T(nLogn). On Thu, Jun 30, 2011 at 7:22 PM, sunny agrawal <[email protected]>wrote: > it can be done without sorting(Finding any other traversal) > > Do it recursively, > last element of the traversal will be head, and now if you will see in the > traversal left part of the traversal will be its LST and Right will be RST > (except Head) only thing you need to find will be the index of the element > which divides the traversal into LST and RST. this index can be find very > easily beacause all elements of LST are less than root value. > > > On Thu, Jun 30, 2011 at 7:16 PM, Nishant <[email protected]>wrote: > >> if BST contains integers then sort the postorder traversal which will >> give you inorder traversal... >> >> On Jun 30, 6:27 pm, "oppilas ." <[email protected]> wrote: >> > Is it possible to create a binary search tree (not binary tree) from >> post >> > order traversal only? >> > If give, how and if not please give reason/counter examples. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > Sunny Aggrawal > B-Tech IV year,CSI > Indian Institute Of Technology,Roorkee > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
