GATE CS 2007 Q12 — Trees

The height of a binary tree is defined as the maximum number of edges from the root to any leaf node.

To maximize the number of nodes in a binary tree of height $h$, the tree must be a perfect binary tree where every level is completely filled:

• Level $0$ (root level) has $2^0 = 1$ node.
• Level $1$ has $2^1 = 2$ nodes.
• Level $2$ has $2^2 = 4$ nodes.
• ...
• Level $h$ has $2^h$ nodes.

The total maximum number of nodes $N$ is the sum of nodes at all levels from $0$ to $h$:

Using the formula for the sum of a geometric progression, we get:

Example: For a tree of height $h = 1$, the maximum number of nodes is $2^{1+1} - 1 = 3$ (a root with two children), which matches option C.