Computer Programming                                                                                    Name -
Data Structures Worksheet #2

Answer the following on separate paper. Draw the trees as neatly as possible.

1. Insert the letters I N T E R M E D I A T E S into an initially empty binary search tree, starting with the I and ending with the S. Draw the tree. How many internal nodes have 2 children?

2. Insert the letters S E N I O R D I V I S I O N into an initially empty binary search tree, starting with the S and ending with the final N. Draw the tree. What is the internal path length of the resulting tree?

3. Build a binary search tree with the letters D A T A S T R U C T U R E S, starting with the D and ending with the S. Draw the tree. How many nodes have one child?

4. How many differently shaped binary search trees are possible using the letters A C S L, if the letter L is always the first letter inserted into the tree? Draw all of the the differently shaped trees.

5. What is the length of the shortest internal path possible in a binary tree with 6 internal nodes? Draw a tree with this minimum number of internal nodes.

6. Insert the letters I S T A N B U L into an initially empty binary search tree, starting with the I and ending with the L. Draw the tree. What is the height of the resulting tree?

7. Draw the resulting tree obtained by inserting the letters C O N S T A N T I N O P L E into an initially empty binary search tree, starting with the C and ending with the E. What is the height of the resulting tree?