public class Node> {

private T data;

private Node left;

private Node right;

public Node(){

data = null;

left = null;

right = null;

}

public Node(T t){

data = t;

left = null;

right = null;

}

public T getData() {

return data;

}

public void setData(T data) {

this.data = data;

}

public Node getLeft() {

return left;

}

public void setLeft(Node left) {

this.left = left;

}

public Node getRight() {

return right;

}

public void setRight(Node right) {

this.right = right;

}

public void addNode(Node newNode){

}

@Override

public String toString(){

}

}

Code: Binary Search Tree

import java.util.ArrayList; public class BinarySearchTree> { private Node root; public void add(T t){ } public boolean find(T data){ } public void removeRight(T t){ } public void removeLeft(T t){ } public static > ArrayList sort(ArrayList list){ } public static > void inOrderSort(ArrayList list, Node node){ } @Override public String toString(){ } public static void main(String[] args){ } } 

---------------------------------------------------------------------------------------------

Activity 1: Add

First, download the files Node.java and BinarySearchTree.java from Resources > Lab Files > Lab 13. Here you will find the basics for a binary tree. Look over both classes and make sure that you understand what is provided, specifically why for the generic we have > (ask the TA if you are not sure). You will need to complete the addNode method for the Node class. If you need a reminder of how add works in a Binary Search Tree, please review the lecture notes or ask a TA. Remember that T is of type Comparable, think about what this allows us to use. Next complete the add method in the BinarySearchTree class, think about what happens when the root is null.

Activity 2: Print

Next complete the toString method in both classes. The string should return the in-order traversal of the tree (subtree for the node class). Use the main method of the BinarySearchTree class to test your add method by creating at least 5 Node objects and one tree. The String or Integer classes are good for testing. Remember that when a BinarySearchTree is traversed in-order the output should be in sorted order, use this to test your code.

Activity 3: Find

Next write the find method in the BinarySearchTree class. Find is very similar to add except that you are simply looking for the node and not adding it (technically you are looking for the data that is passed in).

Activity 4: Remove

As we know from class there are two different ways to remove a node in a Binary Search Tree (assuming it has two children). We can either remove (1) the largest value in the left subtree, or (2) the smallest value in the right subtree. You will need to implement two methods, one called removeRight which will replace the node being removed with the correct value from the right subtree and removeLeft which will replace the node being removed with the correct value from the left subtree. Remember that there are other cases that need to be handled. For example, when the node has no children or when it has only one child. For the remove method we first need to find the node containing the data and then remove, of course how we remove it depends on how many children it has. Hint 1: A while loop can help to find the value needed to replace the node being removed. Be sure to keep track of two nodes while looping. Hint 2: We don't really need to replace the node, only the data contained in it. Hint 3: There is a corner case that you need to keep in mind, for example, what happens when the first node in the right subtree doesn't have a left child (also think about a similar case for the left subtree).

Activity 5: Sort

From before we know that an in-order traversal of a Binary Search Tree will visit the nodes in sorted order. We are going to use this to our advantage to sort an ArrayList. For this we will have two methods, the sort method that takes in an ArrayList of values to sort and returns a new ArrayList with the sorted values. The second, inOrderSort, will take in an ArrayList and a Node and will traverse the subtree of the given node, in-order, adding elements to the ArrayList. This second method is almost identical to the toStirng method that you wrote earlier except that instead of creating a String of the data you will add the data to the ArrayList. In the sort method you will need to add all the elements to a BinarySearchTree, create a new empty ArrayList and pass both of these to the inOrderSort method.

Because both of these methods are static the generic used in both should be different from the one in the class. The > is needed to allow the static method to handle generics, otherwise the method header is the same as other methods.

Finally test your sort method in the main method. After your sort method is working correctly in your tests analyse the code and try to figure out the complexity class. In addition, time the method with various size inputs (just write a for loop and use the Random class to populate the ArrayList). To time the method use the technique that we used in the Algorithms lab. Are the times that you record consistent with your prediction of the order class? Compare this with the other times you have for other sort methods from the Algorithms lab.