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
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy