The GATE Grind

GATE 2017 CS – Question 16

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

Let $T$ be a binary search tree with 15 nodes. The minimum and maximum possible heights of $T$ are:

Note: The height of a tree with a single node is 0.

  1. 4 and 15 respectively
  2. 3 and 14 respectively
  3. 4 and 14 respectively
  4. 3 and 15 respectively

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) 3 and 14 respectively

Explanation

The shortest tree is a perfectly balanced one. A complete binary tree with 15 nodes has 4 full levels, so its height is 3. The tallest tree is a chain of 15 nodes, whose height is 14.