GATE CS 2015 Set 2 Q10 — Trees

In any binary tree, there is a direct relationship between the number of leaf nodes (nodes with degree 0) and the number of nodes with exactly two children.

Let:

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

The total number of nodes in the tree is:

Since every node except the root has exactly one incoming edge, the total number of edges in a tree with $N$ nodes is $N - 1$. We can also count the total number of edges by summing the outgoing degrees of all nodes:

Equating the two expressions for the total number of edges:

Substitute Equation 1 into Equation 2:

Simplifying the equation by subtracting $n_1 + n_2$ from both sides:

Given that the number of leaves $n_0 = 20$:

Thus, the number of nodes in $T$ having two children is 19.