[algogeeks] Re: given a bst and a value x.find pair of nodes in the tree that sum upto x

[bittu]

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.