Project #5 (Binary Search Trees)

CMSC 132

Due Date: Friday Nov 4, 6:00 pm

Object-Oriented Programming II

Type of Homework: Closed

Fall 2005


This homework has several objectives.  Those objectives are:

This homework is considered a closed homework.  Make sure you read the Open/Closed policy before continuing working on this project.


For this project you will complete the following tasks:

Your project will be graded as follows:

For this project:


Important Restrictions

To make sure that you are not "bypassing" some of the goals of the project, you must abide by the following restrictions in your project implementation.  However you do NOT have to abide by these restrictions while writing your own test cases.

The TAs have been instructed not to help you debug your code unless you have written a test case that demonstrates that your project is malfunctioning.  You should be writing and using your test cases WHILE you are implementing the project, not as an afterthought at the very end.  Testing and software development go hand-in-hand.


Much of the documentation for this project is contained in "JavaDoc" in the project files themselves.  This documentation can be found in the .java files or in Project JavaDoc.


For this project you will implement a "polymorphic" binary search tree. We say the binary search tree is polymorphic because there will be two types of Trees:  EmptyTrees and NonEmptyTrees.  An empty tree contains no fields.  A non-empty tree has four fields:

If a non-empty tree has no left or right child, then instead of having it's left/right reference refer to null, we will have them refer to an EmptyTree.  So both the left and right references of a non-empty tree will always point to another tree -- it's just a question of whether or not that other tree is empty.

When you are implementing various methods, you will notice how convenient this polymorphism is -- you will simply call a method on the left/right child of the current node without having to distinguish whether or not the child is empty or non-empty.

Singleton Design Pattern

If you think about it, all empty trees are alike.  They have no data, so there is no way to distinguish one empty tree from another.  For this reason, we will be employing the "Singleton Design Pattern" in our implementation of the empty tree class.  This means that we will instantiate exactly one instance of the empty tree class.  Anytime a non-empty tree has a missing left/right child, it will refer to this one copy of the empty tree.

Classes You Need to Implement

Performance Report

You must write a one or two page report comparing the performance of the binary search tree vs. the singly linked list.  From lecture you already know the order (Big O notation) associated with each structure.  By writing some tests and examining the CPU time each test takes, show that the binary search tree and the singly linked list behave as specified by the growth-rate function.

The following is additional information regarding the performance report:

Style Requirements

Honor Section Requirements

In addition to the above requirements, you must satisfy the following requirements:


Submit your project using the submit project option associated with Eclipse. 

Academic Integrity

Please make sure you read the academic integrity section of the syllabus so you understand what is permissible in our programming projects.  We want to remind you that we check your project against other students' projects and any case of academic dishonesty will be referred to the University's Office of Judicial Program

Web Accessibility