# M-ary tree problem

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.

-
Could you give a little more information? I didn't understand it, sorry. –  Charlie Nov 10 '12 at 14:38
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.