CSE205 Binary Trees and Recursion

Assignment Objectives

After completing this assignment the student should be able to,

• Implement a simple binary search tree class in Java according to Interface specifications given in UML.
• Implement an in-order traversal algorithm for a binary tree
• Implement a generic type in Java.

Assignment Requirements

For this assignment you are given the following Java source code files:

CSE205_Assignment04.java (This file is complete - you will make no changes to this file)
Tree.java (This file is complete you will make no changes to this file)
BSTree.java (you must complete this file)

The specifications for the files are given below (including the UML diagram on the following page). Special requirements:

BSTree Class

1. insert method

a. Inserts a new item into the binary search tree in the correct location.
b. There should be no duplicate items in the tree. If an item is inserted and that item is already in the tree then this method should simply return without changing the state of the tree.

2. contains method

a. Returns true if the tree contains the specified item; otherwise returns false.

3. printInOrder method

a. Prints the items in the tree in a space separated list in ascending order.

4. toString method

a. Returns a string containing the items in the tree in ascending order and separated by spaces.

Node Class

1. Your BSTree class must contain a nested inner class called Node.

2. This class must have the following attributes:

a. left : Node - representing the left sub-node to this Node object
b. right : Node representing the right sub-node to this Node object
c. data : T holding the data for this Node object

3. This class must have the following methods:

a. Insert(item : T) - this is a recursive method that finds the insertion point and inserts a Node for the new item in the correct position in the sub-tree for which this Node is the root

UML Class Diagram see image.