i donot think that the link provided is for the same problem, the link provides a solution to balance a tree whereas this problem is to merge two BST without any limitation on the balance factor
having said that th balancing the tree itself is an interesting problem and i must say that the documentation is poor here.. (: On 7/27/10, Gene <[email protected]> wrote: > You actually only need a singly linked list. See and old discussion > about this at > > http://groups.google.com/group/comp.programming/msg/41f46b2801c4f84e > > This will do the job in O(n). > > On Jul 26, 11:00 pm, Ashish Goel <[email protected]> wrote: >> Jalaj, >> >> How do you convert a Circular DLL to BST?? >> Please refer my solution, and coorect it if needed;) >> >> Regards >> Ashish >> >> On 7/26/10, jalaj jaiswal <[email protected]> wrote: >> >> >> >> >> >> > suppose both trees contains n nodes >> > then converting to dll both the trees O(n) + O(n) >> > then merging two dll's O(n) >> > converting back to tree also O(2*n)=O(n)......// not sure about it >> >> > code for converting tree to dll >> > node * bsttolist(node *root){ >> > if(root==NULL) return NULL; >> > node *l=bsttolist(root->left); >> > node *r=bsttolist(root->right); >> > root->left=root; >> > root->right=root; >> > append(l,root); >> > append(l,r); >> > return l; >> > } >> >> > here append function merges two circular doubly linked lists , you can >> > make >> > that on your own >> >> > On Mon, Jul 26, 2010 at 5:52 PM, Manjunath Manohar >> > <[email protected] >> >> wrote: >> >> >> @jalaj: could u pls elaborate on that a bit more..will it have the >> >> complexity of O(n logn logn), and also can u provide the pseudocode >> >> pls.. >> >> >> -- >> >> 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]<algogeeks%2bunsubscr...@googlegroups >> >> .com> >> >> . >> >> For more options, visit this group at >> >>http://groups.google.com/group/algogeeks?hl=en. >> >> > -- >> > With Regards, >> > Jalaj Jaiswal >> > +919026283397 >> > B.TECH IT >> > IIIT ALLAHABAD >> >> > -- >> > 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. >> >> -- >> Best Regards >> Ashish Goel >> "Think positive and find fuel in failure" >> +919985813081 >> +919966006652 >> Ho > > -- > 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. > > -- Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 -- 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.
