Question

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. 4
• B. 2
• C. 10
• D. 5

Hint:

Work out the unique shape of the complete (here, perfect) binary search tree that 1 to 15 must form, then check how many ancestors each candidate value has, since every ancestor of a node must be inserted before it.

Answer 1

The Correct Option is D

A different way to see this is to first state a general counting rule connecting a node's depth in the tree to the earliest insertion position it can occupy, and then simply read off each option's depth, instead of hand constructing an explicit insertion order for every option.

General rule: in any binary search tree built by repeated single element insertions into an initially empty tree, a node at depth $d$ (root at depth 0) has exactly $d$ ancestors, and every one of those $d$ ancestors must be inserted strictly before the node itself, since the insertion procedure walks down from the root through each ancestor in turn before reaching the empty slot for the new node. Hence a node at depth $d$ can be inserted no earlier than insertion number $d+1$, and this bound is always achievable by inserting the node's $d$ ancestors first, in root to parent order, immediately followed by the node itself.

Step 1: Fix the tree shape.
As derived from the sorted sequence 1 to 15 splitting at medians, the tree is: root 8 (depth 0); 4 and 12 at depth 1; 2, 6, 10, 14 at depth 2; and the eight leaves 1,3,5,7,9,11,13,15 at depth 3.

Step 2: Apply the general rule to each option.
Value 4 is at depth 1, so its earliest possible insertion position is $1+1=2$, and it can also occupy position 3 by inserting one other independent node first (for example 8, then 12, then 4), so position 3 is achievable. Value 4 can be third.
Value 2 is at depth 2, so its earliest achievable position is $2+1=3$, achieved by inserting its two ancestors 8 and 4 first. Value 2 can be third.
Value 10 is at depth 2, so its earliest achievable position is 3, achieved by inserting 8 and 12 first. Value 10 can be third.
Value 5 is at depth 3, so its earliest possible position is $3+1=4$. No insertion order can place a depth 3 node earlier than position 4, because doing so would require fewer than 3 of its ancestors to already be present, which is impossible. So value 5 can never occupy position 3 or earlier.

Step 3: Conclusion.
The general depth based bound shows values at depth 1 or depth 2 (options A, B, C) can all reach position 3, while the depth 3 leaf value 5 (option D) cannot, confirming the same answer reached by explicit construction.$$ \boxed{5 \ \text{(Option D)}} $$