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 7b 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.

FIGURE 7 Two binary search trees containing the same data as the tree in Figure

(b) Brett Brittany Dong Jared Jim Megan Whitney