0
$\begingroup$

A full K-ary tree is a tree where every internal node has exactly K children. Use mathematical induction to prove that the number of leaves in a non-empty full K-ary tree is (K − 1)n + 1, where n is the number of internal nodes.

How can I prove it?

$\endgroup$
0

2 Answers 2

1
$\begingroup$

A proof indeed is a simple induction with respect to the height $h$ of the tree. Denote by $n_h$ the number of internal nodes of a complete $K$-ary tree and by $l_h$ the number of its leaves. At the base of induction for $h=1$ we have $n_h=1$ and $l_h=K$, so the formula $l_h=(K-1)n_h+1$ is verified. At the induction step each leaf of a tree of height $h$ becomes an internal vertex, but generates $k$ leaves of a tree of a height $h+1$. Thus $n_{h+1}=n_h+l_h$ and $$(K-1)n_{h+1}+1=(K-1)(n_h+l_h)+1=(K-1)n_h+1+(K-1)l_h=Kl_h=l_{h+1}.$$

$\endgroup$
1
$\begingroup$

You can prove this by induction on the number of internal nodes (rather than the overall height).

With zero internal nodes, you only have the root node, which is thus a leaf and with $n=0$ the formula gives $(K-1)0+1 = 1$ leaf as expected.

Now for such a tree $T$ with $n+1$ internal nodes, there must be at least one internal node which has only leaves as children, found by simply moving up the internal nodes until there is none above the final selected internal node. Now we can compare the leaf count $L(T)$ and internal node count to the qualifying tree $T'$ produced by removing all $K$ leaves from this selected node (thus becoming a leaf). $L(T) = L(T') + K -1$ and since $T'$ has $n$ internal nodes (down from $n+1$) $L(T') = (K − 1)n + 1$ by the inductive hypothesis and $$L(T) = (K − 1)n + 1 +K-1 = (K − 1)(n+1) + 1$$ as required.

$\endgroup$

You must log in to answer this question.