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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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.