Exercise 12.2.4

Professor Bunyan thinks he has discovered a remarkable property of binary search trees. Suppose that the search for key kk in a binary search tree ends up in a leaf. Consider three sets: AA, the keys to the left of the search path; BB, the keys on the search path; and CC, the keys to the right of the search path. Professor Bunyan claims that any three keys aAa \in A, bBb \in B, and cCc \in C must satisfy abca \le b \le c. Give a smallest possible counterexample to the professor's claim.

In the tree below, B={4,2,1}B = \{4, 2, 1\} and C={3}C = \{3\}, but for b=4b = 4 and c=3c = 3 we don't have bcb \le c.