More precisely, your class should have public methods insert(Comparable) and traverse() that respectively add the given element to the tree and traverse the tree in inorder by retuning a List that contains the data elements in the appropriate order. It should also have three constructors as described below, and methods getCounter() and resetCounter() that return and reset to zero the current count of element comparisons. Any method of the class that makes an comparison between two elements of the tree should increment this counter.

The insert method should return true if the item to be inserted was not in the tree, and false if it was. In the latter case, it should not perform the duplicate insertion.

One of the three constructors for the class should simply construct an empty binary search tree. This constructor should take no arguments. A second constructor should take an ArrayList and insert its elements one by one, in the given order, into an initially empty binary search tree. The third constructor should also take an ArrayList and insert elements one by one into an initially empty binary search tree, but it should first apply a randomizing permutation to the input list. This constructor should take a second parameter which is a Random object to control the randomizing, and a third boolean parameter which has value true if the input list is not to be mutated by the randomizing permutation, and false if it is. A simple algorithm for randomizing an ArrayList is to consider each array position from left to right, and for each position randomly choose an element with index greater than or equal to the given position and swap the element into the given position.

ClassCastExceptions may arise in your insertion methods, randomization methods, and constructors. You needn't try to handle this class of exceptions in these methods as long as you document that the methods may throw exceptions of this class.

You may define any other additional classes and methods that you find helpful. It is recommended that you use a BinaryNode class along the lines of the Weiss text. In general, you may use the Weiss text -- and any code or algorithm that I provide for you -- for guidance if you give proper credit.

Note that the coding standards for this section of CS 146 discourage (1) public instance variables, (2) unrestricted public mutators, and (3) the use of default protection for classes.

For full credit, you should use message passing in any auxiliary methods, rather than passing nodes or trees as arguments as in the BinaryNode methods of Weiss's Figure 4.17. There will be a small penalty if you use Weiss's strategy.

When performing and counting element comparisons, you should avoid comparing the same two elements more than once, as, for example, the Weiss text does in Figure 4.18. In any case, you might want to compare your counts of comparisons with the theoretical worst-case and average-case values.