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 23-19b 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?