1. This is not a valid binary search tree. What’s wrong with it?

          32
         /  \
        16  45
       /  \
      5   38 
       

2. Use the Binary Search Tree insertion algorithm to insert the keys 1, 2, 3, 4, 5, 6, 7 into a initially empty BST (in that order!).
   
   
   
   
   
   

   1. What is the height of the resulting tree?
      
      
      

   2. What is the (exact) average number of nodes that must be visited to find a value that is in this tree assuming that all values 1-7 are equally likely to be searched for? (Remember: An average case analysis is performed by adding up the costs for each possible case, then dividing by the number of cases.)
      
      
      

   3. In general, if I add the numbers 1 through n to a binary tree (in order), what is the average number of nodes that will be accessed during the find operation in the resulting tree?
      
      
      

3. Draw the binary search tree with the smallest possible height containing the keys 1, 2, 3, 4, 5, 6, 7.
   
   
   
   
   

   1. What is the height of the tree?
      
      
      
   2. What is the (exact) average number of nodes that must be visited to find a value that is in the tree assuming that all values 1-7 are equally likely to be searched for?
      
      
      
   3. In general, if I add the numbers 1 through n to a maximally-balanced binary tree, what is the average running time of the find operation? (A big-\(\Theta\) answer is fine.)
      
      
      
   4. List the values of the tree nodes in the order the nodes are visited in a preorder, inorder, and postorder traversal of the tree.
      
      
      
   5. Which of these gives the order in which nodes should be added to a new BST to obtain the minimum height?
      
      
      
   6. Draw your tree as it will appear after remove(4) is called.
      
      
      
      
      

4. Here is an interface describing a simple Dictionary ADT:

   public interface Dictionary<K, V> {
   
     /**
      * Insert an entry into the dictionary. Return the previous value, or null if
      * there was no previous value associated with this key
      */
     V put(K key, V value);
   
     /**
      * Return the value associated with the provided key, or null if this key is not
      * in the dictionary.
      */
     V get(K key);
   
     /**
      * Remove the indicated entry from the dictionary. Returns true if something was
      * actually removed.
      */
     boolean remove(K key);
   
     /**
      * Return true if the provided key is in the dictionary.
      */
     boolean contains(K key);
   
     /**
      * Return the number of entries in the dictionary.
      */
     int size();
   
   }

   • Consider two concrete implementations of this ADT:
     1. Key/value pairs are stored in a sorted array. Lookups are performed using binary search.
     2. Key/value pairs are stored in a binary search tree.
   • What are the worst-case big-\(\Theta\) running times for the following operations. For “BST” assume the worst-case tree structure, for “Balanced BST” assume that the tree remains balanced.

   	insert	remove	find
   Array
   BST
   Balanced BST

   • Which implementation do you think makes the most sense? Array or BST?