Suppose that you have n values to put into an empty binary search tree. a. In how many different orders can you add the n values to the tree? This is not the same as the number of possible binary...

Suppose that you have n values to put into an empty binary search tree.

a. In how many different orders can you add the n values to the tree? This is not the same as the number of possible binary search trees for n values. Explain why.

b. Figure 24-20b shows a binary search tree that effectively acts like a sorted list. In how many different orders can you add the n values to the tree such that every parent has only one child?

Such a tree has worst-case performance.

c. What is the probability that a randomly constructed binary search tree has worst-case performance? Hint: Compute the fraction of the total number of possible orders that results in the worst case.