CSc 150

1. Answer the following questions using the binary search tree shown below.
   
   1. List all of the nodes on level 3.
   2. If this tree were implemented using an array, what index would the node containing 5 be stored in?
   3. List all of the siblings of the node that contains 4.
   4. List the nodes in the order in which they would be visited using a preorder traversal.
   5. Repeat part (d), but using an inorder traversal.
   6. Examine your answer to part (e). In general, when an inorder traversal is performed on any binary search tree, what is the order of visitation?

2. Write the following method in the BinarySearchTree class:

   public String toString()

   which returns the contents of the BST in postorder as a printable string. You should write this method recursively, calling upon a private helper method:

   private String toString(BSTnode N)

   to get the job done. You may assume that each BSTnode object contains a toString method that can be called upon to give you the node's data as a string. You may also assume that BinarySearchTree contains a single private instance variable:

   private BSTnode root;

   You may actually want to write this method in Eclipse to make sure you get it right.

3. Insert the following ints into a 2-3 tree in the order given. Redraw the tree after each insertion to show what it would look like. If any nodes split, show what the tree would look like both before and after the split occurs.

   Order of insertions: 26, 15, 48, 30, 35, 28, 20, 1, 27

Gentle Reminder