Question 50

We are inserting the 7 distinct keys $\{1, 2, 3, 4, 5, 6, 7\}$ into an empty binary search tree.

The problem states that the height of a single-node tree is 0. A tree with $n = 7$ nodes has height 6 if and only if the tree is completely degenerate (every internal node has exactly one child, forming a single chain or path of 7 nodes).

Analyze the conditions on the insertion sequence to form a degenerate BST:

1. The first inserted key (the root) must be either the minimum element (1) or the maximum element (7) of the set. If any intermediate element were chosen, keys would fall on both sides of the root, creating both left and right subtrees and resulting in a height strictly less than 6. Thus, there are 2 choices for the root.

2. After the first key is placed, the remaining 6 keys must form a single contiguous chain. At each step $i$ (for $i = 1, 2, \dots, 6$), the next key to be inserted must again be either the minimum or the maximum of the currently remaining uninserted keys. This gives 2 choices at each step.

3. For the final (7th) key, only 1 key remains, so there is 1 choice.

The total number of valid insertion permutations is: