## Question

You are to code a binary search tree. A binary tree is a collection of nodes, each having a data item and a reference pointing to the left and right child nodes. What makes a binary tree a binary search tree is that it must follow the order property: for any given node, its left child and all of its children must be less than the current node while its right child and all of its children 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: the no-argument constructor (which should initialize an empty tree), and a constructor that takes in data to be added to the tree, and initializes the tree with this data. Any attempts to add data that is already in the tree should be ignored (the tree shouldn't be changed, and the duplicate item shouldn't get added).

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

Recursion

Since trees are naturally recursive structures, all methods that are not 0(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. These wrapper methods will just call another private helper method that is recursive. 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's 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. The BSTNode class will be given to you; do not modify it.

Methods

You will implement all standard methods for a Java data structure (add, remove, etc.) in addition to a few other methods. Some of these methods are functions that you'd expect from a BST (such as the traversals) while some of the other ones serve more as practice BST recursion problems for you.

Traversals

You will implement 4 different ways of traversing a tree: pre-order traversal, in-order traversal, post-order traversal, and level-order traversal. The first 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. A leaf node has a height of 0. Based on this recursive definition, this means that null nodes would have a height of -1.

Comparable

As stated, the data in the BST must implement the Comparable interface. As you'll see in the java files, the generic typing has been specified to require that it implements the Comparable interface. You use the interface by making a method call like data1. compare To (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 > data2.

If negative, then data1 < data2.

If zero, then data1 equals data2.

Do note that the returned value can be any integer in Java's int range, not - 0, 1 as you may have seen in some examples.

## Solution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

import java.util.*;/**

* Your implementation of a binary search tree.

*

* @author YOUR NAME HERE

* @userid YOUR USER ID HERE

* @GTID YOUR ID HERE

* @version 1.0

*/

public class BST<T extends Comparable<? super T>> {

// DO NOT ADD OR MODIFY INSTANCE VARIABLES.

private BSTNode<T> root;

private int size;

/**

* A no-argument constructor that should initialize an empty BST.

*

* Since instance variables are initialized to their default values, there

* is no need to do anything for this constructor.

*/

public BST() {

// DO NOT IMPLEMENT THIS CONSTRUCTOR!

}

/**

* Initializes the BST with the data in the Collection. The data

* should be added in the same order it is in the Collection.

*

* Hint: Not all Collections are indexable like Lists, so a regular for loop

* will not work here. However, all Collections are Iterable, so what type

* of loop would work?

*

* @param data the data to add to the tree

* @throws IllegalArgumentException if data or any element in data is null

*/

public BST(Collection<T> data) {

if(data == null){

throw new IllegalArgumentException("Cannot insert null data into data structure.");

}

Iterator<T> iterator = data.iterator();

while (iterator.hasNext()){

add(iterator.next());

}

}

/**

* Add the data as a leaf in the BST. Should traverse the tree to find the

* appropriate location. If the data is already in the tree, then nothing

* should be done (the duplicate shouldn't get added, and size should not be

* incremented).

*

* Should have a running time of O(log n) for a balanced tree, and a worst

* case of O(n).

*

* @throws IllegalArgumentException if the data is null

* @param data the data to be added

*/

public void add(T data) {

if(data == null){

throw new IllegalArgumentException("Cannot insert null data into data structure.");

}

if(root == null) {

root = addNode(root, data);

}else {

addNode(root, data);

}

}

/**

* This adds the data to the root node specified at node.

*

* @param node the root node of subtree

* @param data the data to be added

* @return the node to be added.

*/

private BSTNode<T> addNode(BSTNode<T> node, T data){

if(node == null){

size++;

return new BSTNode<>(data);...

By purchasing this solution you'll be able to access the following files:

Solution.java.