@Rahil: you are correct....thanks On 24 July 2010 18:33, rahul patil <rahul.deshmukhpa...@gmail.com> wrote:
> 1> convert the BST into a sorted doubly linklist.(increasing order) It > will take O(n) time. > > 2> Now find two nodes in a link list whose sum is k(given no) > > to find sum in linklist. take two pointers ptr1= head ptr2=tail of > linlist. > > now find sum of ptr1->data + ptr2-> data > > while(ptr1->data < ptr2-> data){ > if ((ptr1->data + ptr2-> data )>k) > ptr2= ptr2->prev; > else if ((ptr1->data + ptr2-> data )<k) > ptr1= ptr1->next; > else if ((ptr1->data + ptr2-> data ) == k){ > print_data_of_ptr1_and_ptr2; > ptr2= ptr2->prev; > ptr1= ptr1->next; > } > } > > > the 2nd step will take O(n) time.No added space complexity > > > > > > > > On Jul 24, 9:29 am, Priyanka Chatterjee <dona.1...@gmail.com> wrote: > > Given a binary search tree of n nodes, find two nodes whose sum is equal > to > > > > > a given number k in O(n) time and constant space. > > > (ignoring recursion stack space) > > > > > I have got O(nlogn) time , O(1) space and O(n) time, O(n) space. > Please > > > help me out with O(n) time and O(1) space. > > > > > -- > > > Thanks & Regards, > > > Priyanka Chatterjee > > > Final Year Undergraduate Student, > > > Computer Science & Engineering, > > > National Institute Of Technology,Durgapur > > > India > > >http://priyanka-nit.blogspot.com/ > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Thanks & Regards, Priyanka Chatterjee Final Year Undergraduate Student, Computer Science & Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.