Suppose we constructed the binary search tree shown below by starting with an empty tree and inserting one element at a time from an input sequence, without any rotations or other manipulations. Which of the following assertions about the order of elements in the input sequence cannot be true?

(A) 8 came after 3 and 19 came after 29

(B) 7 came before 8 and 23 came after 37.

(C) 1 came after 12 and 29 came before 42.

(D) 3 came before 14 and 16 came before 28

Answer: D

28 is an ancestor of 16, so 16 must have come after 28. In the tree only ancestordescendant relationships matter in determining the order in which elements arrive. An ancestor must always come before any of its descendants. Incomparable elements could come in any order.