@Rahil: you are correct....thanks
On 24 July 2010 18:33, rahul patil <[email protected]> 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 <[email protected]> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> 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 [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.
