Exercise 12.2.4
Professor Bunyan thinks he has discovered a remarkable property of binary search trees. Suppose that the search for key in a binary search tree ends up in a leaf. Consider three sets: , the keys to the left of the search path; , the keys on the search path; and , the keys to the right of the search path. Professor Bunyan claims that any three keys , , and must satisfy . Give a smallest possible counterexample to the professor's claim.
In the tree below, and , but for and we don't have .