GATE CS 2016 Set 2 Q40 — Binary Search Trees

A binary search tree (BST) with $7$ nodes has a height of $6$ if and only if it is a skewed binary tree (a chain where every internal node has exactly one child).

To construct such a tree through sequential insertions:

1. The first inserted element (the root) must be either the minimum or the maximum of the $7$ elements. This ensures all remaining elements go to one side (either entirely to the left or entirely to the right subtree). Thus, there are $2$ choices.
2. The second inserted element must be either the minimum or the maximum of the remaining $6$ elements. This gives $2$ choices.
3. This pattern continues for each subsequent insertion. For the $i$-th insertion (where $1 \le i \le 6$), we have exactly $2$ choices (the minimum or the maximum of the remaining elements).
4. For the last ($7$-th) element, only $1$ choice remains.

Therefore, the total number of valid insertion sequences is: $$2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 1 = 2^{7-1} = 2^6 = 64$$