Solution should be-
each node has three values
1) root_cur
2)cur_fleaf
3)cur_sleaf
strcut ret_ele
{
largest;
second_largest
}
ret_ele solve(node,sum_root_cur)
{
if(node==root&&root==NULL)
{
sum_root_cur=0;
return;
}
root_cur=sum_root_cur
if(node->left=0&&node->right==0)
return (ret_ele(node->data,0));
ret_ele l=solve(root->left,sum_root_cur+1);
ret_ele r=solve(root->right,sum_root_cur+1);
//find max 2 elements from l->cur_fleaf,l->cur_sleaf,
r->cur_fleaf,r->cur_sleaf
// return these two element
}
On 6/23/11, Jitendra singh <[email protected]> wrote:
> I think this solution is wrong .
> Because
> for the case -
> 1
> 5 8
> 100 300 10
> ans should be 406
> But above code gives 124
>
>
>
>
>
> On 6/22/11, Anantha Krishnan <[email protected]> wrote:
>> I modified Sunny's code to get Node X and Node Y.
>> http://ideone.com/YF9qi
>>
>> Can we do better than this?
>>
>> Thanks & Regards,
>> Anantha Krishnan
>>
>> On Wed, Jun 22, 2011 at 11:11 AM, oppilas .
>> <[email protected]>wrote:
>>
>>> Sunny,
>>> Can but can we modify this code to get the *node X and node Y*?.
>>>
>>>
>>>
>>> On Wed, Jun 22, 2011 at 8:32 AM, Anantha Krishnan <
>>> [email protected]> wrote:
>>>
>>>> @sunny agrawal
>>>> *Thanks a lot.*
>>>> *Great code. I got the logic now.Thanks again.*
>>>> *
>>>> *
>>>> Thanks & Regards,
>>>> Anantha Krishnan
>>>>
>>>> On Tue, Jun 21, 2011 at 11:52 PM, sunny agrawal
>>>> <[email protected]>wrote:
>>>>
>>>>> see this
>>>>> *
>>>>> https://ideone.com/1ZtIq*
>>>>>
>>>>>
>>>>> On Tue, Jun 21, 2011 at 10:23 PM, Anantha Krishnan <
>>>>> [email protected]> wrote:
>>>>>
>>>>>> Thanks.
>>>>>> I expect more details in implementation point of view.
>>>>>>
>>>>>> Thanks & Regards,
>>>>>> Anantha Krishnan
>>>>>>
>>>>>>
>>>>>> On Tue, Jun 21, 2011 at 6:41 PM, sunny agrawal
>>>>>> <[email protected]
>>>>>> > wrote:
>>>>>>
>>>>>>> @Piyush
>>>>>>> good to start with
>>>>>>> But i think a recursive O(n) is possible
>>>>>>> in downward calls pass sum from root to node
>>>>>>> and on return calls pass sum from leafs to root of each subtree and
>>>>>>> using this collective information updating a global ans max.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> On Tue, Jun 21, 2011 at 5:05 PM, Piyush Sinha <
>>>>>>> [email protected]> wrote:
>>>>>>>
>>>>>>>> i am assuming all nodes have positive values..
>>>>>>>>
>>>>>>>> Keep a buffer of all the leaf nodes..take two leaf nodes and find
>>>>>>>> the
>>>>>>>> LCA..compute sum from root to LCA and subtract it from the sum of
>>>>>>>> nodes from
>>>>>>>> root to the leaves...store all the sums and find maximum out of
>>>>>>>> it..
>>>>>>>>
>>>>>>>> On Tue, Jun 21, 2011 at 4:52 PM, Anantha Krishnan <
>>>>>>>> [email protected]> wrote:
>>>>>>>>
>>>>>>>>> Hi All,
>>>>>>>>>
>>>>>>>>> Given a binary tree, find 2 leaf nodes say X and Y such that
>>>>>>>>> F(X,Y)
>>>>>>>>> is maximum where F(X,Y) = sum of nodes in the path from root to X
>>>>>>>>> +
>>>>>>>>> sum of
>>>>>>>>> nodes in the path from root to Y - sum of nodes in the common path
>>>>>>>>> from root
>>>>>>>>> to first common ancestor of the Nodes X and Y.
>>>>>>>>>
>>>>>>>>> Any ideas.
>>>>>>>>>
>>>>>>>>> Thanks & Regards
>>>>>>>>> Anantha Krishnan
>>>>>>>>>
>>>>>>>>> --
>>>>>>>>> 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.
>>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> --
>>>>>>>> *Piyush Sinha*
>>>>>>>> *IIIT, Allahabad*
>>>>>>>> *+91-8792136657*
>>>>>>>> *+91-7483122727*
>>>>>>>> *https://www.facebook.com/profile.php?id=100000655377926 *
>>>>>>>>
>>>>>>>> --
>>>>>>>> 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.
>>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> --
>>>>>>> Sunny Aggrawal
>>>>>>> B-Tech IV year,CSI
>>>>>>> Indian Institute Of Technology,Roorkee
>>>>>>>
>>>>>>>
>>>>>>> --
>>>>>>> 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.
>>>>>>>
>>>>>>
>>>>>> --
>>>>>> 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.
>>>>>>
>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> Sunny Aggrawal
>>>>> B-Tech IV year,CSI
>>>>> Indian Institute Of Technology,Roorkee
>>>>>
>>>>> --
>>>>> 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.
>>>>>
>>>>
>>>> --
>>>> 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.
>>>>
>>>
>>> --
>>> 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.
>>>
>>
>> --
>> 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.
>>
>>
>
--
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.
