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.

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

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented Oct 27, 2021 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.
    Commented Oct 27, 2021 at 5:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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