1. Convert your Binary tree into doubly linked list. 2. Sort the linked list using merge sort 3. Build BST using doubly linked list by each time selecting middle node and recursively calling left part of linked list and right part of linked list.
On Tue, Aug 7, 2012 at 10:23 PM, vaibhav shukla <vaibhav200...@gmail.com>wrote: > Hi all > > The problem is to convert a binary tree into Binary Search Tree > > My approach was : > > 1. Store the Inorder traversal of BT in an array. > 2. Sort the array in ascending order. > 3. Again do inorder traversal and write the Node's data from array one by > one. > > This approach takes O(n) extra space. > Can someone tell a better approach that doesn't require any extra space. > Thanx. > > -- > best wishes!! > Vaibhav > > -- > 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. > -- 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.
