if the tree has parent pointer then we can apply similar approach,,
increment and decrenent... and can also be done in O(1)
have to poninters pointed to the min and max nodes and them move pointers by
checking the sums..
On Fri, May 14, 2010 at 5:03 PM, anna thomas <annathoma...@gmail.com> wrote:
> @rohit: Divya's soltn works in this way, if the sum of 2 nos is less than
> req sum, increment the 1st ptr(ptr at beginning of array). If sum > req sum,
> then decrement the 2nd ptr(ptr at end of array)
> In ur example: ptr1 pts to 1 and ptr2 to 123456 (sum > 6)
> dec ptr2 1+4 = 5 (sum < 6)
> inc ptr2: 2+4 =6 (got the ans)
>
> But the qs mentions that it should be in O(1) space.
> Regards,
> Anna
>
>
>
> On Fri, May 14, 2010 at 4:20 PM, Rohit Saraf <rohit.kumar.sa...@gmail.com
> > wrote:
>
>> @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
>>
>>
>>
>> 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<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.
