GATE 2026 CS1 Q.33: solution and answer

Official answer: 11Source: Official answer key, GATE 2026 CS1 (IIT Guwahati)

1. A full binary tree requires every node to have exactly 0 or 2 children (no node has exactly 1 child).

2. If there are $i$ internal (2-child) nodes, the number of leaves is $i+1$, so the total number of nodes is $n=i+(i+1)=2i+1$.

3. For $n=23$: $2i+1=23\Rightarrow i=11$ internal nodes, and leaves $=12$.

4. To maximise height, make the tree as skewed as possible: chain the internal nodes down one side of the tree, so each internal node (except the last one in the chain) has one leaf child and one child that continues the chain.

5. Place the 11 internal nodes at depths $0,1,2,\dots ,10$. The internal nodes at depths $0$ through $9$ each spawn one leaf child (using 10 leaves) and one child continuing the chain to the next depth.

6. The internal node at depth 10 is the last internal node in the chain — it cannot continue the chain (that would require a 12th internal node, leaving too few nodes to keep $n=23$), so both of its children are leaves, at depth 11.

7. Leaf count check: $10$ leaves from the chain (depths $0$–$9$) $+2$ leaves from the last internal node $=12$ leaves, matching $i+1=12$.

8. The longest root-to-leaf path passes through all 11 internal nodes (depths $0$ to $10$) and ends at a leaf at depth 11, i.e. it has 11 edges.

9. So the maximum possible height is $i=11$, consistent with the general result ${\text{height}}_{\max }=\frac{n-1}{2}=\frac{23-1}{2}=11$ for a full binary tree with $n$ nodes.