Question 1. Create a basic, generic DataTree class. As described, it will consist of a binary tree structure, and will need the usual internal node structure and constructor.

Question 2. Write the other methods used in Section One of the commented-out test code in Main. should work as follows:

• The size() and height() methods should return the number of nodes in the tree, and its overall height (longest path). These should both work in constant O(1) time, with no need of recursion or iterative looping. Recall that height is measured by number of edges, so a tree with only a root node has height() == 0, and the one in the image above has height() == 2. (If the tree is empty, we will say it has height() == -1.)

• The add() method should take in an element of the tree's generic type T and add it to the tree in the proper location (i.e., so that the tree is always complete). This will guarantee that the trees are always of minimal height for their size. Addition of elements should be no worse than O(log n) time. This is especially important for the large Integer- typed trees: if your add() method spends a lot of time searching in the tree for the next place to add an element in level-order, this will be far too slow. It is possible to write a method that can always find the next place to insert an element in no more than log n iterations, and never has to search the entire tree. In fact, add() could be written to work in constant O(1) time, too (although this requires an increase in the memory usage of the objects). For this application, I recommend shooting for O(log n).

Question 3. Write the printLevels() method used in Section Two of Main. This method should print out the requisite number of levels in the tree. Remember that the first level of a tree (the root) is at level 0, so there will always be height() + 1 total levels. Your method should print out each level separately, matching the format given in the sample output file.

Question 4. Write the methods used in Section Three of Main:

• The equals() method should take in a tree of the same generic type, and return true if and only if the two trees contain the same elements, in the same level-order .

This method should run in no worse than O(n log n) time at worst.

• The clear() method should remove all elements from the tree, so that after it has run the tree will have size() == 0 again.

Question 5. Write the methods used in Section Four of Main. To do this, you will have to make your tree class properly Iterable, with the usual Iterator implementation inside it. Done properly, use of the Iterator (either explicitly or implicitly) will result in a level-order access of n elements in no worse than O(n log n) time.

Question 6. Write the coded needed for Section Five of Main. This involves writing another class, called DataFile, as follows:

• The class will extend the basic File type.

• The class will be typed generically, so that it can save tree data to a binary file, and then load it back in again. The type of the class will be restricted to only those types that conform to java.io.Serializable. (A Serializable object is one that can be saved to binary data.)

• The save() method will take in a tree of the same type as the file, and then write the node data (not the nodes themselves, with all of their linking references, but just the data elements) to the corresponding file (named when the DataFile() constructor is run). The data-file that is written will consist of a single integer value, giving the number of data-elements in the file, followed by each of those data-elements, one by one. To write this file, you should use the java.io.ObjectOutputStream class, which allows you to write both primitive objects and more complex types to a file-stream. (Documen- tation found on-line.) If you do this part correctly, you should get the same size values back for the resulting files as reported in the sample output. In addition, a binary file with the name given to the constructor should appear in your Java project folders as usual when creating the file. Note that the file will not be a human-readable text-file, but will instead consist of raw byte data.

• The load() method will also take in a tree of the same type as the file, and then will re-open the saved data-file (assuming it already exists), and use an ObjectInputStream to read in the number of objects in it (the initial integer saved to that file), and then read those objects back in one-by-one, placing them into the tree.

Question 7. Finally, write the code required for Section Six of Main. This involves writing the IntDataFile class, as follows:

• This class, like the previous one, will extend File, but it will not be generically typed. Instead, it presumes that every data element will be of Integer type.

• It will use DataOutputStream and DataInputStream to write and read Integer data.

• When saving data to a file, it does not need to save an extra integer to give the number of data elements in the file. Instead it can use the length of the file (in bytes), and the known size of a Java integer, to calculate this number, before looping to load data back into a tree.