GATE CS 2009 Q37 — Binary Search Trees

To find the maximum height of an AVL tree with $n = 7$ nodes, we can determine the minimum number of nodes required to construct an AVL tree of height $h$, denoted as $N(h)$.

Given that the height of a single-node tree is $0$:

• For $h = 0$: $N(0) = 1$ (a single root node)
• For $h = 1$: $N(1) = 2$ (a root with one child)

For any height $h \ge 2$, an AVL tree of minimum size consists of a root, one subtree of height $h-1$ with minimum nodes, and another subtree of height $h-2$ with minimum nodes. This gives the recurrence relation:

Using this recurrence, we compute the minimum nodes for successive heights:

• $N(2) = N(1) + N(0) + 1 = 2 + 1 + 1 = 4$
• $N(3) = N(2) + N(1) + 1 = 4 + 2 + 1 = 7$
• $N(4) = N(3) + N(2) + 1 = 7 + 4 + 1 = 12$

Since we have exactly $7$ nodes, the maximum height we can achieve is $3$ (which requires exactly $7$ nodes). A height of $4$ would require at least $12$ nodes.

Thus, the maximum height of an AVL tree with $7$ nodes is 3.