Consider a binary tree π in which every node has either zero or two children.β¦
2025
Consider a binary tree π in which every node has either zero or two children. Let π > 0 be the number of nodes in π.
Which ONE of the following is the number of nodes in π that have exactly two children?
- A.
\(\frac{n - 2}{2}\) - B.
\(\frac{n - 1}{2}\) - C.
\(\frac{n }{2}\) - D.
\(\frac{n + 1}{2}\)
Attempted by 193 students.
Show answer & explanation
Correct answer: B
Answer: the number of nodes with exactly two children is (n - 1)/2.
Derivation:
Let I be the number of nodes that have exactly two children (internal nodes).
Let L be the number of leaves (nodes with zero children).
Total nodes n = I + L.
Each internal node has two children, so the total number of child links is 2I. Those child links account for every node except the root, so 2I = n - 1.
Solve 2I = n - 1 to get I = (n - 1)/2.
Remark: this also implies n = 2I + 1, so n is always odd for such trees.
A video solution is available for this question β log in and enroll to watch it.