BST: want level order?? note some minor changes needed (e.g., return type of traversal)??

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.

no search?? using counters?? The insert method should return true if the item to be inserted was not null and not in the tree, and false if it was null or was in the tree. In the latter case, it should not perform a duplicate insertion.

test?? 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 a BinaryTree and convert it to an AVL tree. For full credit, this constructor should have linear time complexity in the size of the binary tree.

A linear-time algorithm for constructing an AVL tree from a binary tree is to first traverse it to an array or array list, then install the midpoint of the list as the root of the AVL tree, and process recursively the sublists to the left and right of the midpoint. Note that no insertion is required. For reduced credit, you may instead traverse the binary tree and insert each element individually into an initially empty AVL tree. This method will not have linear time complexity.

may use BST from A1 or from Weiss, may use AVL code from Weiss or from my posted solutions for earlier semesters, should always credit. As in the text, you needn't try to handle ClassCastExceptions that result from comparing incomparable elements.

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.

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.