Professor Bunyan thinks he has discovered a remarkable property of binary search trees. Suppose that the search for key k in a binary search tree ends up in a leaf. Consider three sets: A, the keys to the left of the south path; B, the keys on the search path; and C, the keys to the right of the search path. Professor Bunyan claims that any three keys a ( A, b ( B, and c ( C must satisfy a ‰¤ b ‰¤ c. Give a smallest possible counterexample to the professors claim.

Figure 1: Counter example to Professor Bunyan's claim. The set A is empty. The search path, where search is performed for the key 3 is marked. The search proceeds from root 8 to the node 4 and this to node 3. So B = (8, 4, 4) Set C is the only key to the right of the path, i.e., C = (8).

Transcribed Image Text:

Set B (8 Set C Set A (3.