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:

   // The Dictionary Interface.
   interface Dictionary<K, V> {
   
       // Reinitialize dictionary
       void clear();
   
       // Insert a record
       // k: the key for the record being inserted.
       // e: the record being inserted.
       void insert(K key, V value);
   
       // Remove and return a record.
       // k: the key of the record to be removed.
       // Return a matching record. If multiple records match "k", remove
       // an arbitrary one. Return null if no record with key "k" exists.
       V remove(K key);
   
       // Return a record matching "k" (null if none exists).
       // If multiple records match, return an arbitrary one.
       // k: the key of the record to find
       V find(K key);
   
       // Return the number of records 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?