GATE 2010 CS (CS1) – Question 20
In a binary tree with n nodes, every node has an odd number of descendants, counting itself. How many nodes have exactly one child?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) 0
Explanation
A node with one child would have subtree size one plus the odd size of that child’s subtree, which is even. That contradicts the condition that every node has odd subtree size. Thus no node has one child, answer zero, A.