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?
Answer: B. \(\frac{n - 1}{2}\) — 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).…
- A.
\(\frac{n - 2}{2}\) - B.
\(\frac{n - 1}{2}\) - C.
\(\frac{n }{2}\) - D.
\(\frac{n + 1}{2}\)
Attempted by 271 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.
Explore the full course: Iocl Engineers Officers Grade A Paper 2