GATE CS 2015 Set 1 — Question 25

The height of a tree is defined as the length of the longest root-to-leaf path, which is the number of edges in that path. A tree with a single node has a height of 0.Maximum number of nodes:
A binary tree of a given height $h$ has the maximum number of nodes when it is a full binary tree. In a full binary tree of height $h$, every level is completely filled with nodes.
The number of nodes at level $i$ is $2^i$ (assuming root is at level 0).
The total number of nodes for a height $h$ is the sum of nodes at all levels from 0 to $h$:$$N_{max} = \sum_{i=0}^{h} 2^i = 2^{h+1} - 1$$For a height of $h=5$, the maximum number of nodes is:$$N_{max} = 2^{5+1} - 1 = 2^6 - 1 = 64 - 1 = 63$$Minimum number of nodes:
A binary tree of a given height $h$ has the minimum number of nodes when it is a skewed tree (either left-skewed or right-skewed). In a skewed tree, each node has at most one child, forming a single path.
To achieve a height of $h$, there must be a path of length $h$, which requires $h+1$ nodes.
For a height of $h=5$, the minimum number of nodes is:$$N_{min} = 5 + 1 = 6$$Therefore, the maximum and minimum number of nodes in a binary tree of height 5 are 63 and 6, respectively. This corresponds to option (A).