Question

Show that a full \({\bf{m - }}\)ary balanced tree of height \(h\) has more than \({{\bf{m}}^{{\bf{h - 1}}}}\) leaves.

Short answer

T has more than \({m^{h - 1}}\) leaves.

Step-by-step solution

Definition

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

A m-ary tree of height h is balanced if the leaves are at levels h or h-1.

The level of a vertex is the length of the path from the root to the vertex.

Denoting the vertices

Given: A full m-ary balanced tree T of height h

To proof: T has more than \({m^{h - 1}}\) leaves.

Let \(m \ge 2\).

Since the tree is of height h, there exists vertices at level h. Let us denote the number of vertices at level h as p (\(p \ge 2\) as \(m \ge 2\)). Note that these p vertices are all leaves.

Step 3: \({\bf{T}}\) has more than leaves \({{\bf{m}}^{{\bf{h - 1}}}}\)

Let T’ be the tree T with all p vertices at level h removed. T’ then has height h-1 and T’ then has to be a complete m-ary tree (since it can only contain leaves at level h-1).

One knows that a complete m-ary tree T’ of height h-1 has \({m^{h - 1}}\) leaves.

The tree T then contains more than \({m^{h - 1}}\) leaves, because T is the tree T’ with m leaves add to some of the leaves in T’ and \(m \ge 2\).