Disproving Professor Bunyan's hypothesis on Binary search tree

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 ∈ Ab ∈ 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.

counter-example to Professor Bunyan's claim

One thought on “Disproving Professor Bunyan's hypothesis on Binary search tree”

Leave a Reply

Your email address will not be published. Required fields are marked *

Notify me of followup comments via e-mail. You can also subscribe without commenting.