Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A full $m$-ary tree $T$ has 81 leaves and height 4

1) Give the upper and lower bounds for $m$

2) What is $m$ if T is also balanced?

[with $m^h=l$ for maximum leaf in a m-ary tree $m^4=81$ then m=3 , how to find other m?] I know m>2 and m<22 with attempt.

share|improve this question
    
Could you give a little more information? I didn't understand it, sorry. –  Charlie Nov 10 '12 at 14:38

1 Answer 1

up vote 0 down vote accepted

You already gave the answers.

If the tree is balanced and has height 4 then the tree has $m^4$ leaves. This is easy to see since you have $m$ node in the 1st layer, $m^2$ in the second, $m^3$ in the third, and $m^4$ in the 4th layer, which contains the leaves. Hence the answer for 2.) is $m=3$, since $3^4=81$. Moreover, $m\ge 3$ is a lower bound, because the balanced tree is the case that contains the maximal number of leaves.

The other extremal case is when the tree is a caterpillar. A caterpillar is a tree whose non-leave nodes form a path . In your case a caterpillar has $3(m-1)+m$ leaves. This gives $m\le84/4=21$ as an upper bound.

share|improve this answer
    
thanks. can you explain more about "2)What is m if T is also balanced?" and about caterpillar? –  geni Nov 10 '12 at 21:12
    
@ing: I thought the answer was very clear. Anyway I extended my answer. If you still have problems, say what exactly you don't understand. –  A.Schulz Nov 11 '12 at 11:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.