GATE CS 2025 Set 2 Q3 — Trees

In a binary tree $T$, let:

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

According to the problem, every node in $T$ has either zero or two children. Therefore, the number of nodes with exactly one child is:

The total number of nodes $n$ is given by:

For any binary tree, the relationship between the number of leaf nodes ($n_0$) and the number of nodes with two children ($n_2$) is always:

Substituting Equation 2 into Equation 1, we get:

Thus, the number of nodes with exactly two children is $\frac{n-1}{2}$.