This is nice. There is also an article on how to do this iteratively with a stack:
http://groups.google.com/group/comp.programming/msg/41f46b2801c4f84e This solution actually traverses a BST of any shape, tears it apart, and reassembles it as a perfectly balanced tree. However, it will also work on a sorted list. Just replace the BST traversal with a list traversal. On Dec 11, 12:33 pm, Lucifer <sourabhd2...@gmail.com> wrote: > 1) Get the count of nodes in the given DLL. Say its, n. > > 2) Call convert(0, n-1, &headPtrToDLL); > > node* convert(int start, int end, node **head) > { > node * root = NULL; > if (start > end) > return NULL; > int mid = (start + end) / 2; > node * left = convert( start, mid -1, head); > root = *head; > (*head) = (*head)->next; // (*head)->right; > node * right = convert( mid + 1, end, head); > root->left = left; > root->right = right; > return root; > } > > On Dec 11, 12:00 pm, AMAN AGARWAL <mnnit.a...@gmail.com> wrote: > > > > > Hi, > > > WAP to convert a sorted DLL to a balanced BST. > > > Regards, > > Aman. > > > -- > > AMAN AGARWAL > > "Success is not final, Failure is not fatal: It is the courage to continue > > that counts!"- Hide quoted text - > > - Show quoted text - -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
