In a binary tree with n nodes, every node has an odd number of descendants.…
2010
In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?
- A.
\(0\) - B.
\(1\) - C.
\((n- 1 ) / 2\) - D.
\(n - 1\)
Attempted by 504 students.
Show answer & explanation
Correct answer: A
Answer: 0
Key idea: every node's subtree size (number of descendants including itself) is odd.
A leaf has exactly 1 descendant (itself), which is odd.
If a node had exactly one child, that child's subtree size is odd by hypothesis, so the parent’s subtree size would be 1 + (odd) = even, a contradiction.
Therefore no node can have exactly one child, so the number of such nodes is 0.
A video solution is available for this question — log in and enroll to watch it.