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.
