GATE CS 2017 Set 1 Q.6 (CS Q.6): Binary Trees, Binary Search Trees and Balanced Trees

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.

4 and 15 respectively

3 and 14 respectively

4 and 14 respectively

3 and 15 respectively

Official answer and solution

Solution

Determine the minimum height using a complete binary tree structure and the maximum height using a degenerate chain structure for 15 nodes.

The height of a single-node tree is defined as 0. For a binary tree with $n$ nodes:

The maximum possible height occurs when the tree is degenerate (skewed), where every internal node has exactly one child. In this linked-list structure, a tree with $n$ nodes has $n - 1$ edges from the root to the leaf:

h_{\max} = n - 1 = 15 - 1 = 14

The minimum possible height occurs when the tree is as balanced as possible (a complete binary tree). A perfect binary tree of height $h$ contains $2^{h+1} - 1$ nodes. For $n = 15$ :

2^{h+1} - 1 = 15 \implies 2^{h+1} = 16 \implies h + 1 = 4 \implies h_{\min} = 3

Therefore, the minimum and maximum possible heights of $T$ are 3 and 14 respectively.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.