Re: [algogeeks] converting binary tree to BST
For a balanced tree , use either DLL or array ; same thing . On Wed, Aug 8, 2012 at 10:29 PM, Navin Kumar wrote: > @vaibhav : yes it will be a balanced BST. > > > On Wed, Aug 8, 2012 at 11:29 AM, vaibhav shukla > wrote: > >> @Navin >> >> By your algo of starting with the middle node,I guess a balanced BST >> would be created. Is it ? >> >> >> On Wed, Aug 8, 2012 at 1:24 AM, Navin Kumar wrote: >> >>> 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 >> > 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. >>> >> >> >> >> -- >> 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. > -- - - - - - - - - - - - - With Regards Daksh Talwar -- 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.
Re: [algogeeks] converting binary tree to BST
@vaibhav : yes it will be a balanced BST. On Wed, Aug 8, 2012 at 11:29 AM, vaibhav shukla wrote: > @Navin > > By your algo of starting with the middle node,I guess a balanced BST would > be created. Is it ? > > > On Wed, Aug 8, 2012 at 1:24 AM, Navin Kumar wrote: > >> 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 >> 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. >> > > > > -- > 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.
Re: [algogeeks] converting binary tree to BST
@Navin By your algo of starting with the middle node,I guess a balanced BST would be created. Is it ? On Wed, Aug 8, 2012 at 1:24 AM, Navin Kumar wrote: > 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 > 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. > -- 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.
Re: [algogeeks] converting binary tree to BST
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 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.
[algogeeks] converting binary tree to BST
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.
