GATE CS 2026 Set 1 Q23 — Searching, Sorting, Hashing

A full binary tree (or strict binary tree) is a binary tree in which every node has either $0$ or $2$ children.

To find the maximum possible height $h$ for a given number of nodes $N$, we must construct a tree that is as skewed as possible. In such a tree, each level from level $1$ to level $h$ contains exactly $2$ nodes (one internal node and one leaf node, except the last level which contains two leaf nodes).

The minimum number of nodes $N$ required to achieve a height $h$ in a full binary tree is given by:

For a given number of nodes $N$, the maximum height $h$ satisfies:

Substituting $N = 23$ into the inequality:

Thus, the maximum possible height of a full binary tree with $23$ nodes is $11$.