GATE CS 1995 Q1.17 — Trees

In any binary tree, let:

• $n_0$ be the number of leaf nodes (nodes with degree $0$)
• $n_1$ be the number of nodes with degree $1$
• $n_2$ be the number of nodes with degree $2$

The total number of nodes $N$ in the tree is:

Since a tree with $N$ nodes has exactly $N - 1$ edges, and each edge connects a parent to its child, we can also count the edges by summing the outgoing degrees of all nodes:

Equating the two expressions for the number of edges ($E = N - 1$):

Subtracting $n_1 + n_2$ from both sides simplifies to:

Given that the number of leaf nodes $n_0 = n$, the number of nodes of degree $2$ is:

Therefore, the correct option is B.