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