Read Algorithms 3.2 on BSTs.

Read Algorithms 3.1 and 3.5 on symbol tables.

Complete all of the functions in MyIntSET

Do the following problems from the text. (Not handed in.)

  3.2.2 

    Inserting the keys in the order A X C S E R H into an
    initially empty BST gives a worst-case tree where every node has one
    null link, except one at the bottom, which has two null links. Give
    five other orderings of these keys that produce worst-case trees.

    You can also describe the constraints that produce this outcome
         --- Things like "insert A first, insert B before C, etc."
  
  3.2.3

    Give five orderings of the keys A X C S E R H that, when
    inserted into an initially empty BST, produce the best-case tree.
  
    You can also describe the constraints that produce this outcome
         --- Things like "insert A first, insert B before C, etc."

  3.2.4

    Suppose that a certain BST has keys that are integers between
    1 and 10, and we search for 5. Which sequence below cannot be the
    sequence of keys examined? 

    a. 10, 9, 8, 7, 6, 5
    b. 4, 10, 8, 6, 5
    c. 1, 10, 2, 9, 3, 8, 4, 7, 6, 5
    d. 2, 7, 3, 8, 4, 5
    e. 1, 2, 10, 4, 8, 5

    Typo in the book: (b) should be "4, 10, 8, 7, 5"  not "4, 10, 8, 7, 5, 3"