ABOUND FOR THE NUMBEROF LEAVES INANm-ARYTREE It is often useful to have an upper bound for the number of leaves in an m-ary tree. Theorem 5 provides such a bound in terms of the height of the m-ary tree.
THEOREM 5 There are at most mh leaves in an m-ary tree of height h.
Proof: The proof uses mathematical induction on the height. First, consider m-ary trees of height 1. These trees consist of a root with no more than m children, each of which is a leaf. Hence, there are no more than m1 = m leaves in an m-ary tree of height 1. This is the basis step of the inductive argument. Nowassume that the result is true for allm-ary trees of height less than h; this is the inductive hypothesis. Let T be an m-ary tree of height h. The leaves of T are the leaves of the subtrees of T obtained by deleting the edges from the root to each of the vertices at level 1, as shown in Figure 15.
Each of these subtrees has height less than or equal to h − 1. So by the inductive hypothesis, each of these rooted trees has at most mh−1 leaves. Because there are at most m such subtrees, each with a maximum of mh−1 leaves, there are at most m · mh−1 = mh leaves in the rooted tree. This finishes the inductive argument.
