Let $P$ be the set of all integers from 1 to 15. Consider any order of insertion of the elements of $P$ into a binary search tree that creates a complete binary tree. Which one of the following elements can NEVER be the third element that is inserted?

A complete (and here, perfect) binary search tree containing the $15$ elements $\{1, 2, \dots, 15\}$ has a fixed structure uniquely determined by the BST property:

• Level 0 (Root): $8$

• Level 1: Left child of $8$ is $4$; Right child of $8$ is $12$

• Level 2:

  • Children of $4$: Left is $2$, Right is $6$

  • Children of $12$: Left is $10$, Right is $14$

• Level 3 (Leaves): $1, 3, 5, 7, 9, 11, 13, 15$

For any node to be inserted in the BST, all of its ancestors must be inserted before it:

1. The 1st element inserted must be the root, which is $8$.

2. The 2nd element inserted must be one of the direct children of $8$, which can be $4$ or $12$.

3. The 3rd element can be:

   • If the 2nd element was $4$: the 3rd element can be $12$ (child of $8$), $2$ (child of $4$), or $6$ (child of $4$).

   • If the 2nd element was $12$: the 3rd element can be $4$ (child of $8$), $10$ (child of $12$), or $14$ (child of $12$).

Thus, the possible third elements inserted are $\{2, 4, 6, 10, 12, 14\}$.

To insert $5$, all of its ancestors ($8$, $4$, and $6$) must already be present in the tree. This requires at least $3$ elements inserted prior to $5$, so $5$ can at earliest be the $4^{\text{th}}$ element inserted.

Therefore, $5$ can never be the third element inserted.