@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 <prashant.r.k...@gmail.com>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 <sweetdivya....@gmail.com>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 <jalaj.jaiswa...@gmail.com> 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 algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> 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 algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> 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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > 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 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.
