GATE CS 2010 Q10 — Trees

Let $D(u)$ denote the number of descendants of a node $u$. By definition, a node is its own descendant, so we can express $D(u)$ recursively as:

where $D(u_{\text{left}}) = 0$ if the left child does not exist, and $D(u_{\text{right}}) = 0$ if the right child does not exist.

We are given that for every node $u$ in the binary tree, $D(u)$ must be an odd number. Let's analyze the three possible cases for any node $u$:

1. $u$ is a leaf node (0 children):
   $D(u) = 1 + 0 + 0 = 1$, which is odd. (Valid)
2. $u$ has exactly two children:
   Since both children are nodes in the tree, their descendant counts $D(u_{\text{left}})$ and $D(u_{\text{right}})$ must both be odd.
   $D(u) = 1 + \text{odd} + \text{odd} = \text{odd}$, which is odd. (Valid)
3. $u$ has exactly one child:
   Without loss of generality, let $u$ have only a left child. Since the left child is a node, its descendant count $D(u_{\text{left}})$ must be odd.
   $D(u) = 1 + D(u_{\text{left}}) + 0 = 1 + \text{odd} = \text{even}$.
   This contradicts the given condition that $D(u)$ must be odd for every node.

Thus, no node in the tree can have exactly one child. The number of such nodes is $0$.