Consider a binary tree \(T\) in which every node has either zero or two children. Let \(n \gt 0\) be the number of nodes in \(T\).
Which ONE of the following is the number of nodes in \(T\) that have exactly two children?
Answer
(B)
Explanation
Let \(k\) be the number of nodes with two children; all other nodes are leaves. Count the edges in two ways:
- each of the \(k\) internal nodes has 2 child edges, giving \(2k\) edges;
- every node except the root has exactly one edge to its parent, giving \(n - 1\) edges.
So \(2k = n - 1\), that is, \(k = \frac{n-1}{2}\). For example, a root with two leaf children has \(n = 3\) and \(k = 1\). Such a tree always has an odd number of nodes, so \(\frac{n}{2}\) and \(\frac{n-2}{2}\) are not even whole numbers, while \(\frac{n+1}{2}\) counts the leaves.
Answer: B