Project ForgeData Structures
Trees
GATE 2015
Easy
The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are
- 63 and 6, respectively
- B64 and 5, respectively
- C32 and 6, respectively
- D31 and 5, respectively
Explanation
Maximum nodes for height h: a complete binary tree has 2^(h+1)−1 nodes = 2⁶−1 = 63. Minimum nodes for height h: a degenerate 'straight line' tree needs exactly h+1 = 6 nodes to reach that height (one node per level from root to the single leaf).
Source: GATE CS 2015 (Session 1 / 7th Feb Shift 1) (2015)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.