GATE 2026 CS (CS1) – Question 33
The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree. The maximum possible height of a full binary tree with 23 nodes is _________. (answer in integer)
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 11
Explanation
In a full binary tree (strictly binary tree), every internal node has exactly 2 children.
If a full binary tree has $N$ nodes:
$$N = 2k + 1$$
where $k$ is the number of internal nodes, and $k + 1$ is the number of leaves.
For $N = 23$ nodes:
$$2k + 1 = 23 \implies 2k = 22 \implies k = 11 \text{ internal nodes}$$
To maximize the height $h$, each level from level 0 to level $h - 1$ should contain exactly 1 internal node and 1 leaf child, and level $h$ contains the 2 leaf children of the internal node at level $h - 1$.
This configuration uses exactly 1 internal node at each level from 0 to $h - 1$, giving:
$$\text{Total internal nodes} = h = 11$$
Thus, the maximum possible height is $h = \frac{N - 1}{2} = \frac{23 - 1}{2} = 11$.
The correct answer is 11.