GATE 2024 DA Q.52: solution and answer

Official answer: A, B, CSource: Official answer key, GATE 2024 DA (IISc Bengaluru)

1. Take the height $H$ as the number of edges on the longest root-to-leaf path. This is the convention under which the key holds. A single node has $H=0$. A binary tree means every node has at most 2 children. Let $n_0=L$, $n_1$, $n_2$ be the numbers of nodes with 0, 1 and 2 children. Then $I=n_1+n_2$ and $N=n_0+n_1+n_2$.

2. Count the edges two ways. Every node except the root has exactly one parent edge, so there are $N-1$ edges. Each node with $k$ children contributes $k$ edges, so there are also $n_1+2n_2$ edges. Hence $N-1=n_1+2n_2$. Substituting $N=n_0+n_1+n_2$ gives $n_0=n_2+1$.

3. (A) $L=n_2+1\le (n_1+n_2)+1=I+1$ because $n_1\ge 0$. Always true.

4. (B) The longest path alone contains $H+1$ nodes, so $N\ge H+1$, with equality for a chain. Level $d$ holds at most $2^d$ nodes and levels run from $0$ to $H$, so $N\le {\sum }_{d=0}^H{2}^d=2^{H+1}-1$, with equality for a full tree. Always true.

5. (C) Every node on the longest path except its last node (a leaf) has a child, so it is internal. That gives $H$ internal nodes, so $I\ge H$. Internal nodes cannot lie on level $H$, because a node at level $H$ has no children. So they lie on levels $0$ to $H-1$, and $I\le {\sum }_{d=0}^{H-1}{2}^d=2^H-1$. Always true, including $H=0$, where $I=0$.

6. (D) Take a chain of height $H=2$: it has $L=1<H$, so $H\le L$ fails. Also a full tree of height $H$ has $L=2^H>2^{H-1}$, so $L\le 2^{H-1}$ fails too. Not always true.

7. So the statements that are always true are A, B and C.