GATE CS 1992 Q02 — Trees

Let $h$ be the height of the $2-3$ tree (where the root is at level $0$ and the leaves are at level $h$). Since all leaves are at the same depth, we can analyze the tree structure based on $h$:

• Case 1: $h = 2$
  Let the root have $c_0$ children, where $c_0 \in \{2, 3\}$. Each of these children is an internal node at level 1, which must have either $2$ or $3$ leaf children.
  • If $c_0 = 2$, the maximum number of leaves is $3 + 3 = 6 < 9$.
  • If $c_0 = 3$, the only way to get $9$ leaves is if each of the $3$ internal nodes has exactly $3$ children ($3 + 3 + 3 = 9$).
  The total number of internal nodes is $\text{root} + \text{level 1 nodes} = 1 + 3 = 4$. This matches Option A.
• Case 2: $h = 3$
  Let $N_2$ be the number of internal nodes at level 2. These nodes must produce $9$ leaves, so: $$2x + 3y = 9$$ where $x$ and $y$ are the number of level 2 nodes with $2$ and $3$ children respectively, and $N_2 = x + y$.
  • If $y = 3$, then $x = 0 \implies N_2 = 3$. However, we cannot form $3$ nodes at level 2 from level 1 because the minimum children from a root of degree $\ge 2$ is $2 + 2 = 4$.
  • If $y = 1$, then $x = 3 \implies N_2 = 4$. We can form $4$ nodes at level 2 if the root has $2$ children, and each of those has $2$ children ($2 + 2 = 4$).
  The total number of internal nodes is $\text{root} + \text{level 1 nodes} + \text{level 2 nodes} = 1 + 2 + 4 = 7$. This matches Option D.
• Case 3: $h \ge 4$
  The minimum number of leaves for height $h \ge 4$ is $2^4 = 16 > 9$, so no solutions exist here.

Thus, the possible number of internal nodes is $4$ or $7$.