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 binary tree (in order), what is the average number of nodes that will be accessed during the find operation?
   
   
   

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.
   
   
   

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.

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