0
$\begingroup$

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.

  • 0
    Could you give a little more information? I didn't understand it, sorry.2012-11-10

1 Answers 1

0

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.

  • 0
    @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.2012-11-11