Question

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?

Accepted Answer

The correct answer is (A) 0. A node's subtree size (its own descendant count) equals 1 + (left subtree size) + (right subtree size), counting only existing children. If a node had EXACTLY ONE child, its subtree size = 1 + (that child's subtree size). Since every node's descendant count must be odd, the child's count is odd, making 1+odd=even — contradicting the requirement that THIS node's own count also be odd. So no node can have exactly one child.

Explanation