If a full m-ary tree has i internal vertices, how do we find the minimum number of total vertices? I found the formula n = mi + 1, but I'm not sure if this is for full m-ary trees or complete m-ary trees. For example, would a full 5-ary tree with 100 internal vertices have 501 vertices total?
Finding minimum vertices for m-ary tree given i internal verticies.
graph theorytrees
Related Question
- [Math] Full 4-ary tree with 58 internal nodes
- [Math] How to prove that the number of leaves in a non-empty full K-ary tree is (K − 1)n + 1
- In the minimum number of simple paths in a forest of k trees with n vertices
- Smallest number of vertices of degree $1$ in tree with $3$ vertices of degree $4$ and $2$ of degree $5$
Best Answer
Your formula is correct. To see why, suppose you have a full $m$-ary tree $T$. Since the tree is full, each node has either $m$ children or $0$ children. Note that to count all $n$ nodes, it suffices to count all children, then add 1 at the end to account for the root node (the root is not the child of any node). If we have $i$ internal nodes, we have $i$ nodes with $m$ children, so $i\cdot m$ total children. So $n = i m +1$.