GATE CS 1998 Q2.11 — Trees

To find the number of leaves $L$ in a complete $n$-ary tree with $x$ internal nodes, we can use the relationship between the total number of nodes, internal nodes, and edges.

Method 1: Using Node and Edge Relations

1. Let $N$ be the total number of nodes in the tree. Since every node is either an internal node or a leaf, we have: $$N = x + L$$
2. In a complete $n$-ary tree, every internal node has exactly $n$ children. Therefore, the total number of children in the tree is $n \cdot x$.
3. Since every node in the tree except the root is a child of some node, the total number of nodes is also given by: $$N = n \cdot x + 1$$

Equating the two expressions for $N$:

Solving for $L$:

Method 2: Verification with an Example

Let $n = 2$ (a complete binary tree) and $x = 1$ (only the root is an internal node, having $2$ children).

• The number of leaves $L$ is $2$.
• Substituting $n = 2$ and $x = 1$ into the options:
• Option A: $1 \cdot (2 - 1) + 1 = 2$ (Correct)
• Option B: $1 \cdot 2 - 1 = 1$
• Option C: $1 \cdot 2 + 1 = 3$
• Option D: $1 \cdot (2 + 1) = 3$

Thus, the correct option is A.