Algorithms | Misc | Question 16

In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is: 

(A)

nk

(B)

(n – 1) k+ 1

(C)

n( k – 1) + 1

(D)

n( k – 1)

Answer: (C)
Explanation:

For an k-ary tree where each node has k children or no children, following relation holds L = (k-1)*n + 1 Where L is the number of leaf nodes and n is the number of internal nodes. Let us see following for example

k = 3
Number of internal nodes n = 4
Number of leaf nodes = (k-1)*n  + 1
                     = (3-1)*4 + 1
                     = 9 

Quiz of this Question
Please comment below if you find anything wrong in the above post