On 5/2/07, Karthik Singaram L <[EMAIL PROTECTED]> wrote: > > I guess it was a slight difference in terminology...you must have then > phrased the question as "almost complete" rather than a complete tree since > you are allowing the last level to be incomplete. > > Anyways, If the last level is going to be incomplete, then the observe > this..
>>yes >> but the question is to find the height of a complete ternary tree >> sum of the nodes is > 1+3+3^2+3^3+...+3^(h-1)+x > with x<=3^h > This series upon summation gives > The usual stuff... 3^(h-1)(1+1/3+(1/3)^2+...+(1/3)^(h-1)) = > 3^(h-1)*(1-(1/3)^h)/(1-(1/3))=(3^(h)-1)/2 > (3^(h)-1)/2+x = N > Now given N we need h > so > (3^(h)-1)+2x = 2N > Now we substitute that 1<=x<=3^(h) > this gives > (3^(h)+1)<=2N<=(3^(h+1)-1) > So the answer that we are looking for is > ceil(Log_base_3(2N)) > In case you are not satisfied with the proof..check out ceils of > Log_base_3(1(2))=1 > Log_base_3(2(2))=2 > Log_base_3(3(2))=2 > Log_base_3(4(2))=2 > Log_base_3(5(2))=3 > Log_base_3(6(2))=3 > Log_base_3(7(2))=3 > Log_base_3(8(2))=3 > Log_base_3(9(2))=3 > .... > Log_base_3(12(2))=3 > Log_base_3(13(2))=3 > Log_base_4(14(2))=4 > > > > > > > > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
