• 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"
```