Question

How many vertices and how many leaves does a complete \({\bf{m - }}\)ary tree of height \(h\) have?

Short answer

\({{\bf{m}}^{\bf{h}}}\) leaves and \(\frac{{\left( {{{\bf{m}}^{\bf{h}}}{\bf{ - 1}}} \right)}}{{\left( {{\bf{m - 1}}} \right)}}\) internal vertices.

Step-by-step solution

Definition

A tree is a connected graph that does not contain any circuits.

A circuit is a path that begins and ends in the same vertex.

A graph is connected if there exists a path between every pair of vertices.

A full m-ary tree is a tree where every internal vertex has exactly m children.

A complete m-ary tree is a full m-ary tree in which every leaf is at the same level.

Finding the leaves and vertices

A complete m-ary tree of height h has one vertex at level 0,m vertices at level \(1, m \times m = {m^2}\) vertices at level \(2,...,m\) vertices at level h as each internal vertex has exactly m children.

Since every leaf in the complete m-ary tree is at the same level, all leaves are at level h (which is the height of the tree) and thus there are \({m^h}\) leaves.

A full m-ary tree with l leaves have \(n = \frac{{\left( {ml - 1} \right)}}{{\left( {m - 1} \right)}}\) vertices and \(i = \frac{{\left( {l - 1} \right)}}{{\left( {m - 1} \right)}}\) internal vertices. In this case, \(l = {m^h}\) and thus the tree has \(\frac{{\left( {{{\bf{m}}^{\bf{h}}}{\bf{ - 1}}} \right)}}{{\left( {{\bf{m - 1}}} \right)}}\) internal vertices.