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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.