Question 40

A complete binary tree with $15 = 2^4 - 1$ nodes is a perfect binary tree of height $3$. Since the inorder traversal of the BST must be $1, 2, \dots, 15$, the unique BST structure has:

• Depth 0 (root): $8$
• Depth 1: $4$ (left child of $8$) and $12$ (right child of $8$)
• Depth 2: $2, 6$ (children of $4$) and $10, 14$ (children of $12$)
• Depth 3 (leaves): $1, 3, 5, 7, 9, 11, 13, 15$

In any valid BST insertion order that produces this tree, every node must be inserted after all of its ancestors:

• The 1st element inserted must be the root $8$.
• The 2nd element inserted must be at depth 1 ($4$ or $12$).
• The 3rd element inserted can only be at depth 1 or depth 2 (namely $4, 12, 2, 6, 10,$ or $14$).
• Since $5$ is at depth 3 (its ancestors are $8 \rightarrow 4 \rightarrow 6 \rightarrow 5$), all three ancestors $8, 4, 6$ must be inserted before $5$, so $5$ can be at earliest the fourth element inserted.