CPSC 220 Fall 2007
HW 9: 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 to use the removal algorithm discussed in the text -- don't just eyeball it. (The text actually has a limited discussion of how to remove an element, although it does include complete code. You might also want to look at one of the many discussion of this topic online.)

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.