Question

Professor Banyan thinks he has discovered a remarkable property of binary search trees. Suppose that the search for key k in a BST ends up in leaf. Consider three sets (1) set A, the keys to the left of the search path, (2) set B the keys on the search path and (3) set C, the keys on the right of the search path. Professor Banyan claims that any three keys a ∈ A, b ∈ B and c ∈ C must satisy a ≤ b ≤ c . Is his claim true? Otherwise give a counter example to the professor’s claim.

Answer 1

Professor Banyan claim is completely wrong.

The claim of professor Banyan is wrong. Counter example is given below.

Let the key to be searched is 70 then: 

Set A = {45, 55}, B = {40, 50, 60, 70}and C = {} 

Here is very clear that 45 ≤ 40 OR 55 ≤ 50