A complete kary tree is a kary tree analogous to a complete

A complete k-ary tree is a k-ary tree analogous to a complete binary subtree, except that each internal node has k children (not just 2), and all those children are complete k-ary trees of equal height. Write a conjecture about how many leaves are present in a nonempty complete k-ary tree of height h. (c) Prove your conjecture using structural induction.

Solution

Following relationship holds in any k-ary tree in which every node has either 0 or n children.

L = (k-1)*I + 1

Where L is the number of leaf nodes and I is the number of internal nodes.

Proof:
The tree is k-ary tree. Assume it has T total nodes, which is sum of internal nodes (I) and leaf nodes (L). A tree with T total nodes will have (T – 1) edges or branches.

In other words, since the tree is k-ary tree, each internal node will have k branches contributing total of k*I internal branches. Therefore we have the following relations from the above explanations,

k*I = T – 1
L + I = T

From the above two equations, it is easy to prove that L = (k – 1) * I + 1.