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. > > NOTE:The elements in the trees are from two disjont set means the promlem > can be solved from O(log n) but the case is not so, I hope the problem > statement is clear.
The same technique used in http://groups.google.com/group/comp.programming/browse_thread/thread/ecdf69081d071e4e/41f46b2801c4f84e?lnk=st&q=ressler+balance+tree&rnum=2 to balance a tree will work to merge two (or any number) of BSTs in O(n). Disassemble all the trees into sorted lists. Merge all the lists into one. Add the nodes from this list into the new balanced tree as shown. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
