Think hard! It's for a slightly different problem, but the same algorithm works fine. It converts an arbitrarily skewed tree to a perfectly balanced tree. So you can just walk the two input trees, deconstruct them into sorted lists (a fully skewed tree is just a list). Merge the two lists into a single sorted list (as you do in mergesort), then use this to build a new, perfectly balanced tree. Please don't make me code this...
On Jul 27, 10:13 am, Ashish Goel <ashg...@gmail.com> wrote: > 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 <gene.ress...@gmail.com> 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 <ashg...@gmail.com> 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 <jalaj.jaiswa...@gmail.com> 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 > >> > <manjunath.n...@gmail.com > >> >> 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 algoge...@googlegroups.com. > >> >> To unsubscribe from this group, send email to > >> >> algogeeks+unsubscr...@googlegroups.com<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 algoge...@googlegroups.com. > >> > To unsubscribe from this group, send email to > >> > algogeeks+unsubscr...@googlegroups.com. > >> > 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 algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
