1
$\begingroup$

A full $m$-ary tree with $n$ vertices and $i$ internal vertices has $n = m \cdot i + 1$ vertices and $l = (m − 1)i + 1$ leaves.

How can I prove it?

I know that $m$-ary tree is a rooted tree such that every internal vertex has no more than $m$ children. The tree is called a full $m$-ary tree if every internal vertex has exactly $m$ children. An $m$-ary tree with $m = 2$ is called a binary tree.

$\endgroup$
1
  • $\begingroup$ What would be the correct relation instead of l=m-i+1? $\endgroup$
    – Encipher
    Oct 26 '21 at 21:58
1
$\begingroup$

A vertex is either an internal vertex or a leaf. Since the number of all vertices is $n$ while the number of internal nodes is $i$, the number of leaves, $l$ is $n-i$.

Every vertex is identified as a child of an internal node except the root. Since there are $i$ internal node, each of them having $m$ children, the number of vertices, $n$ is $m\cdot i + 1$.

Since $i= n-l$, we also have $n = m\cdot (n-l) + 1$. Or $$(m-1)n = m\cdot l - 1,$$ which is the relation between the number of vertices and the number of leaves in a full $m$-ary tree.

$\endgroup$
2
  • $\begingroup$ I guess root is not an internal node. So when I apply n-i isn't it include root with leaves? $\endgroup$
    – Encipher
    Oct 27 '21 at 4:48
  • 1
    $\begingroup$ As I understand, an internal node is "is any node of a (rooted) tree that has child nodes", although root is indeed a very special internal node. $\endgroup$
    – John L.
    Oct 27 '21 at 5:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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