Question

Let 𝑃 be the set of all integers from 1 to 15. Consider any order of insertion of the
elements of 𝑃 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:

In BST insertion a node's parent must already be in the tree before the node itself can be inserted, so work out which fixed level (root, level 1, or level 2) each candidate value sits at in the unique complete-tree layout of 1 to 15, and check whether that level can be reached by the third insertion.

Answer 1

The Correct Option is D

Step 1: Determine the fixed shape of the final tree. Since P has 15 elements and the final BST is a complete binary tree, it must in fact be a perfect binary tree with 4 levels and height 3 (counting edges) (all 15 positions filled: 1 root + 2 + 4 + 8). Because it is a BST, an in-order traversal must give 1,2,...,15 in sorted order, and the perfect shape fixes every value's position uniquely.

Step 2: Find the value at each fixed position. The median of 1 to 15 is 8, so the root must be 8. The left subtree holds 1 to 7 (median 4, so left child of root = 4), and the right subtree holds 9 to 15 (median 12, so right child of root = 12). Continuing this halving: children of 4 are 2 and 6; children of 12 are 10 and 14; the remaining values 1,3,5,7,9,11,13,15 are the leaves, as children of 2,6,10,14 respectively.

Step 3: Reason about insertion order constraints. The first inserted element must become the root, so it must be 8. The second inserted element becomes a direct child of the root; to land in the correct final position it must be either 4 or 12.

Step 4: Determine which elements can be third. After 8 and (say) 4 are placed, the only empty positions adjacent to the tree are the root's right child (correct value 12) and node 4's two children (correct values 2 and 6). So the third element inserted must be one of 12, 2, 6. Symmetrically, if the second element was 12, the third element must be one of 4, 10, 14. Overall the third element can only be 4, 12, 2, 6, 10, or 14 - never a leaf value, since a leaf's parent (a level-2 node) has not been inserted yet after only two insertions.

Step 5: Check the given options. 4 is possible, 2 is possible, 10 is possible, but 5 is a leaf whose actual parent is 6, so its ancestors 8, 4, and 6 must already exist before 5 can be inserted - impossible after only 2 insertions.

Final Answer: \(\boxed{5 \text{ can never be the third element inserted (Option D)}}\)