GATE CS 2005 Q36 — Trees

We can determine the number of leaves in a complete $k$-ary tree by establishing a relationship between the total number of nodes, internal nodes, and leaves.

Let:

• $n$ = number of internal nodes
• $L$ = number of leaf nodes
• $N$ = total number of nodes in the tree

By definition, the total number of nodes is the sum of internal nodes and leaf nodes:

Since every internal node has exactly $k$ children, the total number of children in the tree is $n \times k$. In any tree, every node except the root is a child of some node. Therefore, the total number of nodes is also given by:

Equating Equation 1 and Equation 2:

Solving for $L$:

Thus, the number of leaves is $n(k-1) + 1$, which corresponds to Option C.