The GATE Grind

GATE 2015 CS – Question 15

Programming and Data Structures · Trees and Binary Search Trees · 1 mark · Multiple choice

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

  1. 63 and 6, respectively
  2. 64 and 5, respectively
  3. 32 and 6, respectively
  4. 31 and 5, respectively

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) 63 and 6, respectively

Explanation

A binary tree of height 5 has levels 0 to 5. It has the most nodes when every level is full, which is $2^6 - 1 = 63$. It has the fewest nodes when it is a single path, which is $5 + 1 = 6$.