Ragupathy M V wrote: > Hi, > Does anybody know how to merge two binary search trees containing n > elements each can be merged in O(n) time.
Seems straightforward. For each BST, put the n elements in a sorted array (by doing an inorder traversal). Then, merge the two lists ala mergesort. Finally, build a (perfectly balanced) BST by recursively putting the median at the root. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---