Binary Search Tree Solution

You are to code a binary search tree, BST, which is a collection of nodes, each having a data item and a reference pointing to a left and a right child nodes. The BST must follow the order property: for any given node, its left child’s data and all of its children’s data must be less than the current node while its right child’s data and all of its children’s data must be greater than the current node. In order to compare the data, all elements added to the tree must implement Java’s generic Comparable interface.

It will have two constructors: a no-argument constructor (which should initialize an empty tree), and a constructor that takes in a collection of data to be added to the tree, and initializes the tree with this collection of data.

You may import Java’s LinkedList/ArrayList classes for the 4 traversal methods and getMaxDataPerLevel, but only for these methods.

Recursion

Since trees are naturally recursive structures, all methods that are not O(1) must be implemented recursively, except for level order traversal. You’ll also notice that a lot of the public method stubs we’ve provided do not contain the parameters necessary for recursion to work, so these public methods act as \wrapper methods" for the user to use. You will have to write private recursive helper methods and call them in these wrapper methods. To reiterate, do not change the method headers for the provided methods.

For methods that change the structure of the tree in some way, we highly recommend you use a technique taught in class called pointer reinforcement. It is not required, but it will make the homework cleaner, and it’ll also help greatly when we get to a later homework.

Nodes

The binary search tree consists of nodes. A class BSTNode is provided to you. BSTNode has getter and setter methods to access and mutate the structure of the nodes.

Methods

You will implement all standard methods for a Java data structure (add, remove, etc.) in addition to a few other methods (such as traversals). You must follow the requirements stated in the javadocs of each method you implement.

Traversals

You will implement 4 di erent ways of traversing a tree: pre-order traversal, in-order traversal, post-order traversal, and level-order traversal. The rst 3 MUST be implemented recursively; level-order is best implemented iteratively. For a level-order traversal, you may use Java’s Queue interface (and an implementing class for it such as LinkedList).

Height

You will implement a method to calculate the height of the tree. The height of any given node is max(left node’s height, right node’s height) + 1. When doing this calculation, a leaf node has a height of 0 and a null node has a height of -1.






4
Homework 4: BST    Due: See Canvas



Comparable

As stated, the data in the BST must implement the Comparable interface. As you’ll see in the les, the generic typing has been speci ed to require that it implements the Comparable interface. You use the interface by making a method call like data1.compareTo(data2). This will return an int, and the value tells you how data1 and data2 are in relation to each other

If positive, then data1 is larger than data2. If negative, then data1 is smaller than data2. If zero, then data1 equals data2.

Note that the returned value can be any integer in Java’s int range, not just -1, 0, 1.


















































5
Homework 4: BST    Due: See Canvas



Grading

Here is the grading breakdown for the assignment. There are various deductions not listed that are incurred when breaking the rules listed in this PDF and in other various circumstances.

Methods:



constructor
4pts


add
14pts


remove
20pts


get
5pts


contains
5pts


preorder
3pts


inorder
3pts


postorder
3pts


levelorder
3pts


height
3pts


clear
2pts


getMaxDataPerLevel
10pts


Other:



Checkstyle
10pts


E  ciency
15pts


Total:
100pts



Provided

The following    le(s) have been provided to you. There are several, but we’ve noted the ones to edit.

    1. BST.java

This is the class in which you will implement the BST. Feel free to add private helper methods but do not add any new public methods, inner/nested classes, instance variables, or static variables.

    2. BSTNode.java

This class represents a single node in the tree. It encapsulates the data, and the left and right references. Do not alter this le.

    3. BSTStudentTest.java

This is the test class that contains a set of tests covering the basic operations on the BST class. It is not intended to be exhaustive and does not guarantee any type of grade. Write your own tests to ensure you cover all edge cases.

Deliverables

You must submit all of the following le(s). Make sure all le(s) listed below are in each submission, as only the last submission will be graded. Make sure the lename(s) matches the lename(s) below, and that only the following le(s) are present. The only exception is that Canvas will automatically append a -n depending on the submission number to the le name(s). This is expected and will be handled by the TAs when grading as long as the le name(s) before this add-on matches what is shown below. If you resubmit, be sure only one copy of each le is present in the submission. If there are multiple les, do not zip up the les before submitting; submit them all as separate les.


6
Homework 4: BST    Due: See Canvas




Once submitted, double check that it has uploaded properly on Canvas. To do this, download your uploaded le(s) to a new folder, copy over the support le(s), recompile, and run. It is your sole respon-sibility to re-test your submission and discover editing oddities, upload issues, etc.

    1. BST.java



























































7