GATE CS 2002 Q2.9 — Trees

Let $L$ be the number of leaf nodes (nodes with $0$ children) and $I$ be the number of internal nodes (nodes with $3$ children).

The total number of nodes $n$ is the sum of leaf nodes and internal nodes:

Since each internal node has exactly $3$ children, the total number of children in the tree is $3I$. In any rooted tree, every node except the root is a child of exactly one node. Therefore, the total number of nodes is also given by:

Solving for $I$:

Substitute the value of $I$ from Equation 2 into Equation 1:

Thus, the number of leaf nodes is $\frac{2n+1}{3}$.

Alternative Verification:

Consider a tree with just a root and its $3$ children ($n = 4$):

• Number of leaf nodes $L = 3$.
• Substituting $n = 4$ into the options:
  • Option A: $\frac{4}{2} = 2$
  • Option B: $\frac{4-1}{3} = 1$
  • Option C: $\frac{4-1}{2} = 1.5$
  • Option D: $\frac{2(4)+1}{3} = 3$

Only Option D matches the correct count.