CPSC 220 Fall 2006
HW 9: More Binary Search Trees

1. In big-O, what is the time required to build a maximum-height (stringy) BST with N elements? Carefully explain your answer.

2. In big-O, what is the time required to build a minimum-height (bushy) BST with N elements? Carefully explain your answer.

3. Consider the BST below:

             20
            /  \
           /    \
          13     40
         /  \    /\
        10  18  30 50
            / \  \
           15 19  35
          /  \   /  \
         14  17  32 38
                     \ 
                     39
   

   Show the tree you get after removing the values below in the order given. Remove each value from the tree as modified so far; e.g., remove 38 from the tree that already has 10 removed, not from the original tree.

   10  38  13  40  20
   

   Be sure that you use the removal algorithm we discussed in class.

4. Could the largest value in a BST be at a leaf? Could it have one child? Could it have two children? Explain your answers.

5. Could the largest value in a BST be at the root? Explain your answer.