@Muthuraj DLL to BST back is not possible In the first step while converting to DLL....we will create a sorted DLL using inorder walk of the tree so DLL will represent the inorder sequence of nodes of BST and we know there can be many BST's for the given inorder so we can not construct the same tree as before.
On Sat, Jul 2, 2011 at 9:06 AM, Muthuraj <sameer.mut...@gmail.com> wrote: > @dave: there is no restriction in the question that we should not > modify the tree. Even otherwise a BST can be constructed from the DLL > recreating the tree. > > On Jun 29, 5:28 pm, Dave <dave_and_da...@juno.com> wrote: > > @Bittu: When you are finishedm can you change the DLL back into the > > original BST? > > > > Dave > > > > On Jun 29, 5:54 pm, bittu <shashank7andr...@gmail.com> wrote: > > > > > > > > > > > > > > > > > Algorithm: > > > 1.Convert BST into sorted DLL which Will Take O(N) Time(Check previous > > > Posts Already Coded) you can see here "cslibrary.stanford.edu/109" > > > 2.take find sum into DLL two pointer start,end which points to > > > starting & end position of DLL. > > > 3. start from start->data & end->data , keep checking until we get all > > > the number that sums to > > > given value as shown > > > while(ptr1->data < ptr2-> data) > > > { > > > if ((ptr1->data + ptr2-> data )>k) > > > ptr2= ptr2->prev; > > > else if ((ptr1->data + ptr2-> data ) > > > ptr1= ptr1->next; > > > else if ((ptr1->data + ptr2-> data ) == k) > > > { > > > print_data_of_ptr1_and_ptr2; > > > ptr2= ptr2->prev; > > > ptr1= ptr1->next;} > > > } > > > > > it will take O(N) time > > > > > Thanks > > > Shashank "I Don't Do Code to Code But I Do Code to Build Product" > > > Computer Science & Engineering > > > Birla Institute of Technology,Mesra > > -- > 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. > > -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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.