@divya : i guess... it wont work.
consider Array {1,2,3,4,123456}
and you want sum 6.@prashant: Is it O(n)? I guess after converting to array and removing all entries > sum, we should start with the smallest element and scan the elements from last till we get some value x which together with the smallest value sums to < sum. Call this position POS1. If we get required sum somewhere in the process, cool ! Else take drop the elements after POS1 and also the smallest element. Recurse on the remaining. -------------------------------------------------- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> On Fri, May 14, 2010 at 3:51 PM, Prashant K <[email protected]>wrote: > i think it can done like this, > assume we have to find 'x' and 'y' wer s='x'+'y' > > 1) select ith node from tree (from beginning to end) > 2) y= s - " ith number (node)" > 3) now search for 'y' in BST if we found then there is node such that s= x > + y; otherwise no.. > > -- Prashant Kulkarni > || Lokaha Samastaha Sukhino Bhavanthu || > || Sarve Jana Sukhino Bhavanthu || > > > > On Fri, May 14, 2010 at 2:47 AM, divya jain <[email protected]>wrote: > >> form a sorted array from inorder traversal of tree. now take to pointers >> one to the beginning of array and other at the end. now check if the sum of >> element is greater than reqd sum then increment 1st ptr. if their sum is >> less than reqd sum then decrement 2nd ptr. if their sum is equal to the reqd >> sum then this is the ans.. >> hope it will work.. >> >> >> On 13 May 2010 20:11, jalaj jaiswal <[email protected]> wrote: >> >>> given a bst... find two nodes whose sum is equal to a number k ... in >>> O(n) time and constant space... >>> >>> -- >>> With Regards, >>> Jalaj Jaiswal >>> +919026283397 >>> B.TECH IT >>> IIIT ALLAHABAD >>> >>> -- >>> 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. >>> >> >> -- >> 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. >> > > -- > 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. > -- 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.
