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.. 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 [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 -~----------~----~----~----~------~----~------~--~---
