Java Assignment

Required to augment the author's Binary Search Tree (BST) code to support these new operations. Method names below are merely suggestions. (The author’s class is attached separately in the file called “authordoc”. I just built a simple test tree in the author’s main method which can be used to test the various operations. )

1. AnyType nthElement(int n) -- returns the n-th element (starting from 1) of the in-order traversal of the BST.

2. int rank( AnyType x ) -- returns the "rank" of x. The rank of an element is its position (starting with 1) in an in-order traversal.

3. AnyType median( ) -- returns the median (middle) element in the BST. If the BST contains an even number of elements, returns the smaller of the two medians.

4. boolean isPerfect( ) -- returns true if the BST is a perfect binary tree.

5. boolean isComplete( ) -- returns true if the BST is a complete binary tree.

6. String toString( int nrLevels ) -- generates the level-order output described in the sample output below.

Most of these operations could easily be implemented by performing an in-order traversal inside the BST and perhaps placing the results in an ArrayList. However, such a method is extremely inefficient. Instead, we are going to achieve faster performance by "augmenting" the BST nodes. You will add a new private integer data member ("tree size") to the BinaryNode which stores the size of the tree rooted at that node (including the root). You must develop your own algorithms for these operations, but obviously you will use the new tree size data member to guide your search. Think before you code and think recursively!

These items cover those topics not addressed elsewhere in the project description. (R) indicates a requirement, (H) indicates a hint, and (N) indicates a note.

1. (R) Although we are only using the BST for integers, the BST must remain a generic class.

2. (R) Duplicate values are not allowed. Attempts to insert a duplicate value should be ignored.

3. (R) Attempts to remove non-existent values should be ignored.

4. (R) From a coding perspective, the easiest way to avoid duplicate insertions or attempting to remove non-existent elements is to first call find( ). However, this technique is NOT permitted for two reasons. Calling find( ) before each insert/remove doubles the running time for these operations and is therefore inefficient. Recusively coding the insert/remove methods to handle these situations is a great learning experience.

5. (R) The level order print (PRINT command) outputs the value of each node, the size of the tree rooted at that node, and the value of the node's parent in that order, inside parenthesis, separated by commas. (node value, tree size, parent value). Since the root has no parent, print NULL for the root's parent value. For readability, separate the levels with a blank line and print no more than 6 node/size/parent values per line. If a level requires multiple lines, use consecutive lines (without a blank line between them).

6. (R) Efficieny counts! Use the most efficient algorithm possible In particular, don't make multiple searches in the tree when one will do. (Yes, we know it doesn't matter from an asymptotic analysis point of view.)

7. (H) Almost all of these operations should be written recursively, but not necessarily all of them.

8. (N) As is customary, your BST class should not provide any methods for printing. However, the BST can provide a method that formats a string containing information that the user wishes to print. Overloading the toString( ) method is a common technique to achieve this kind of functionality.

Note: The instructor noted that once the tree is built, it will not be changed during testing of the program. (just to simplify the task if that helps)