Question

a) Define a full \(m{\bf{ - }}\)ary tree.

b) How many vertices does a full \(m{\bf{ - }}\)ary tree have if it has \({\bf{i}}\) internal vertices\(?\) How many leaves does the tree have?

Short answer

a) A full\(m{\bf{ - }}\)ary tree is a tree where every internal vertex has exactly\({\bf{m}}\)children.

b) Vertices:\({\bf{mi + 1}}\)

Leaves:\({\bf{m(i - 1) + 1}}\)

Step-by-step solution

Using the theorem \({\bf{4(ii)}}\)

A full \(m{\bf{ - }}\)ary tree is a tree where every internal vertex has exactly \(m{\bf{ - }}\) children.

Theorem \({\bf{4(ii)}}\): A full \(m{\bf{ - }}\)ary tree with \({\bf{i}}\) internal vertices has \({\bf{mi + 1}}\) vertices and \({\bf{(m - 1)i + 1}}\) leaves.

Finding the children

A full \(m{\bf{ - }}\)ary tree is a tree where every internal vertex has exactly \({\bf{m}}\) children.

Finding the vertices and leaves

Theorem \({\bf{4(ii)}}\) of section \({\bf{11}}{\bf{.1}}\) Introduction to Trees tells us that a full \(m{\bf{ - }}\)ary tree with \({\bf{i}}\) internal vertices has \({\bf{mi + 1}}\) vertices and \({\bf{(m - 1)i + 1}}\) leaves.