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

Transcribed Image Text:

(b) Brett Brittany Dong Jared Jim Megan Whitney (b) Brett Brittany Dong Jared Jim Megan Whitney

Answer rating: 100% (QA)

A conservative portfolio would typically have a higher proportion of fixed income investments and cash compared to a moderate or aggressive portfolio These types of investments are considered to be le... View the full answer