Question (from Introduction to Algorithms by Cormen et al):
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 search 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 professor’s claim.
I came across this question and was really wondering how do I find a counter-example to this claim which appeared right for my few initial trees that I made. After a few attempts, I was able to give a counterexample. I would suggest that do try a few more times, before you give up and peek into the solution.