CS 223 In-lab 4
Week of 2/13

For CS 223, in-labs will consist of a mix of exercises and problems and short programming assignments.  These will be due at the end of the lab period.  You may occasionally be assigned homework problems as well.  Homework will always be due at the beginning of the next lab.

Exercises (due at the end of lab)

1. Exercise 12.1-1, page 256 of CLRS
2. Exercise 12.2-4, page 260 of CLRS  Hint: You can do this with five nodes labeled {1, 2, ..., 5}

Consider the BinarySearchTree code from class.

3. What sort of input number sequence would lead to an unbalanced tree (worst-case)?
4. Come up with a good insertion sequence for the numbers 1, 2, ..., 15 that leads to a completely balanced binary tree.  Modify the driver so that the numbers are inserted in this sequence and print out the resulting tree.  Is this insertion sequence unique?

What to Turn In

• Answers to above questions, including a printout of the above tree.