unlink each node in original tree in postorder, and insert these nodes in new bst tree
surender On Tue, Nov 8, 2011 at 4:48 AM, vikas <[email protected]> wrote: > @ Above > no need to have another array or nything > binTreeToBST(node *root) > { > if(!root )return; > node *newRoot; > binTreeToBSTConv(root, &newRoot); > } > binTreeToBSTConv(node *old, node *new) > { > if(!old ) return; > binTreeToBSTConv(old->left, new); > binTreeToBSTConv(old->rigth, new); > if(old){ > if(!new) new =old > else{ > insertNode(new, old); > } > } > > } > > On Nov 6, 11:30 am, Anika Jain <[email protected]> wrote: > > @mohit: your algo will add assurance that the tree is balanced.. > otherwise > > ankit's approach is sufficient. > > > > On Sat, Nov 5, 2011 at 8:49 PM, mohit verma <[email protected]> > wrote: > > > another way is : convert binary tree to link list , sort the list and > > > using divide and conquer approach create the BST. > > > > > From link list to BST : find mid of sorted link list , make it root > node > > > and put left of it to recursive(list,start,mid->prev) and > > > root->right=recursive(list,mid->next,last); > > > > > Let me know if something is wrong in this approach. > > > > > On Sat, Nov 5, 2011 at 3:48 PM, ankit agarwal < > > > [email protected]> wrote: > > > > >> I think it's the only way as you need to traverse the entire binary > > >> tree to do it. > > > > >> On Oct 31, 9:45 pm, Ankuj Gupta <[email protected]> wrote: > > >> > How to convert a Binary tree to BST ? Naive way is to create each > node > > >> > of Binary tree one by one and keep on creating the BST. > > > > >> -- > > >> 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. > > > > > -- > > > Mohit > > > > > -- > > > 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. > > -- > 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. > > -- 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.
