Suppose a binary search tree with 5 keys have a height of 3. Note that root is at depth zero.

(a) Draw the best and the worst binary search trees of height 3 that are possible with 5 keys.

(b) Assume that each key in the tree is searched with probability 1/5.

i. What is the expected number of comparisons for a successful search for the best search tree? ii. What is the expected number of comparisons for a successful search for the worst search tree?

(c) What is the expected number of comparisons for an unsuccessful search?

i. What is the expected number of comparisons for an unsuccessful search for the best search tree? ii. What is the expected number of comparisons for an unsuccessful search for the worst search tree?