You are ignoring the possibility that we might want to leave to adjacent levels for a higher-valued descendant.
I think this should be formulated as a DP problem. Writing the recursive version: optimal value of node(at level l) = max of {its value+sum of optimal values of level l+2 , sum of optimal values of all children at level l+1} T(n)=Max{ C_n +Sum_{i=1 to k}(all children at T(n+2)), Sum_{i=1 to k} T(l+1) for all k children We start with T(0) : T(l) : Best solution for level l C_i= Value contained in node i Not sure if notation is explicit.. Explaning with the example tree discussed in prev threads.. 4(1) / \ 1(2) 20(3) / \ / \ 10(4) 5(5) 2(6) 3(7) P.S : no in brackets denote their ids. T(1)= Max{4+T(4)+T(5)+T(6)+ T(7), T(2) + T(3)} T(2) = Max{1, T(4)+T(5)} = Max{1,10+5} = 15 T(3) = Max{20, T(6)+t(7) } = 20 Substituting in T(1), we have T(1) = Max{4+10+2+2, 20+15 } T(1) = 35. A complete solution would have a bottom up approach, storing computed values of tree nodes. I guess its similar to one of the DP problems discussed in CLR, for tree organization. I am not sure if starting from any node is good idea, because we shud maek use of tree organization to eliminate the number of combinations. Hope this helps. ~anshu. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---