0
$\begingroup$

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?

$\endgroup$

1 Answer 1

0
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .