Suppose a binary$-$search tree has n keys and probabilities of searching all keys $($in the tree$)$ are equal. However, probability of NOT finding a key depends on where the search ends, that is$,$ probability of a search ending to the right of the key ki$-1$ and to the left of the key ki is denoted by li$,$ and ai $+$ aj for i $$ j$.$

$($a$)[10$ points$]$ Circle all correct answers for an optimal binary search tree.

i$.$ Since the probability of searching all keys are equal, an optimal binary search tree for these keys is always height balanced

ii$.$ Since the probabilities of all unsuccessful searches are NOT equal, an optimal binary search

tree for these keys is never height balanced.

iii. Since the probabilities of all unsuccessful searches are NOT equal, an optimal binary search

tree for these keys is sometimes height balanced.

iv$.$ None of the above.

$($b$)[10$ points$]$ Explain your one of your selections$).$