Homework help, binary search trees, if you've got nothing better to do.

[GtPrOjEcTX]

I've been working on this one problem for a while (couple hours), can't seem to get it.

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 E A, b E B, c E C must satisfy a<=b<=c. Give a smallest possible counterexample to the professor?s claim.

I can't come up with an example period, let alone the smallest possible. If you've got any hints, ideas, whatever I'd be happy to entertain them as I've run out of ideas.

 

[GtPrOjEcTX]

due in a half hour. no ideas?

 

[gopunk]

row by row:

3
1
02

3 is on the search path, yet not less than 2, which is to the left of the search path

 

[GtPrOjEcTX]

Originally posted by: gopunk
row by row:

3
1
02

3 is on the search path, yet not less than 2, which is to the left of the search path

wow, so simple. can't believe I overlooked that. much thanks.

 

[gopunk]

np

and yes, i had better stuff to do, but then it wouldn't be called procrastination, now would it