# 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. –  HipsterMathematician Nov 10 '12 at 14:38

## 1 Answer

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.

-
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