GATE CS 2015 Set 3 Q25 — Trees

In any binary tree, there is a strict 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 exactly 1 child
• $n_2$ be the number of nodes with exactly 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 edges by looking at the children of each node:

Equating the two expressions for the total number of edges:

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

Given that the number of leaf nodes $n_0 = 200$:

Thus, the number of nodes in $T$ that have exactly two children is 199.