@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.
