Nodes, Children And Leaves

Any node which has children is called internal node. So, In case of tree with more than one node, root node is also an internal node.

Now,let's solve the problem using binary tree. In case of binary tree,k =2. Suppose, binary tree has 7 internal nodes.

ROOT

/ \

N N

/ \ / \

N N N N

/ \ / \ / \ / \

L L L L L L L L

N=Internal Node L=Leaf

So, n = 7 and L=8

(I) nk = 7*2 = 14 wrong

(II) (n-1)k+1 = (7-1)*2+1 = 13 wrong

(III) n(k-1)+1 = 7 (2-1)+1 = 8 right*

(IV) n(k-1) = 7*(2-1) = 7 wrong

Cheers!!

Like Satyabrata I 'solved' the problem by checking a binary tree and ticking the formula which worked. Now that we know this formula works for (at least two!) binary trees it would be nice to prove it for $all$ $k$ _ary trees! I found a simple proof by induction -

Let $L(n)$ be the number of leaves on a complete $k$ _ary tree with $n$ internal nodes. Assume as our hypothesis that, for some number of internal nodes, $r$

$L(r)=r(k-1)+1$

Now choose any leaf, convert it to an internal node and draw from it $k$ branches. This creates one more internal node, destroys one leaf and creates $k$ new leaves. So

$L(r+1)=L(r)+k-1=r(k-1)+1+(k-1)=(r+1)(k-1)+1$

This has the same form as the induction hypothesis with $r$ replaced by $r+1$ .

Note also that the hypothesis holds when $r=1$ because a tree with one internal node (the root) has $k$ branches and $k$ leaves. And indeed our formula gives

$L(1)=1(k-1)+1=k$

Everything is now set up to complete the proof by invoking the principle of mathematical induction to get

$\boxed{L(n)=n(k-1)+1}$

as required.