GATE CS 2017 Set 1 Q6 — Binary Search Trees

To find the minimum and maximum possible heights of a Binary Search Tree (BST) with $n = 15$ nodes, we use the definition that the height of a single-node tree is $0$.

1. Maximum Height

The maximum height occurs when the tree is completely skewed (either left-skewed or right-skewed), where each level contains exactly one node.

For a skewed tree with $n$ nodes, the height is given by:

Substituting $n = 15$:

2. Minimum Height

The minimum height occurs when the tree is as balanced as possible (a perfect binary tree).

For a binary tree of height $h$, the maximum number of nodes it can accommodate is:

We need to find the minimum height $h$ such that the tree can accommodate $15$ nodes:

For $h = 3$, the maximum number of nodes is $2^{3+1} - 1 = 15$. Thus, a perfectly balanced binary tree of height $3$ can accommodate exactly $15$ nodes.

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