GATE CS 2015 Set 1 Q25 — Trees

Given that the height of a tree is the length of the longest root-to-leaf path (measured in terms of the number of edges):

• A tree with height $h = 0$ consists of exactly $1$ node (the root).
• For a binary tree of height $h$:

1. Minimum number of nodes ($N_{\min}$):
The minimum number of nodes occurs when the tree is completely skewed (each internal node has exactly one child).
$$N_{\min} = h + 1$$
For $h = 5$:
$$N_{\min} = 5 + 1 = 6$$

2. Maximum number of nodes ($N_{\max}$):
The maximum number of nodes occurs when the tree is a perfect binary tree (every level is completely filled).
$$N_{\max} = 2^{h+1} - 1$$
For $h = 5$:
$$N_{\max} = 2^{5+1} - 1 = 2^6 - 1 = 64 - 1 = 63$$

Thus, the maximum and minimum number of nodes in a binary tree of height $5$ are $63$ and $6$, respectively.