This project consists of implementing the methods of the EmptyTree, NonEmptyTree, PolymorphicBST, PlaceKeysValuesInArrayLists classes. The complete javadoc for the project can be found at javadoc documentation.

The second part of your project consists of doing a simple performance analysis and writing a short report.


The objective of this project is to implement a polymorphic binary search tree. This project is designed to help you develop your skills at recursion, polymorphism and testing.



Any clarifications or corrections associated with this project will be available at Clarifications.

Code Distribution

The project's code distribution is available by checking out the project named PolymorphicBST. The code distribution provides you with the following:

Binary Search Tree Specifications


Notice that the insert and delete methods on Tree objects return references to Tree objects. In many cases, these functions may return a reference to the this object. However, in some cases they can't. For example. EmptyTree.getInstance.insert("a", "1") has to return an instance of an NonEmptyTree object.

Design and Implementation Restrictions

The above restrictions do not apply to your test cases; you may write them however you wish.


Performance Report

In addition to the above requirements, you must compare the efficiency of PolymorphicBST and java.util.TreeMap classes for both sorted and unsorted inputs. You must then write a report (to be left in the file performaceReport.docx) that consists of two parts:

Web Accessibility