The program BSTTesting.java in the src folder gives you a main method that you can use for

Fantastic news! We've Found the answer you've been seeking!

Question:

The program BSTTesting.java in the src folder gives you a main method that you can use for testing your methods. The program provides a set of calls to build a tree and display values - use it to test your code and debug it before running test cases.

Binary Search Tree methods remove method

In the project folder you will find the BinarySearchTreeMethods file. This file contains skeletons for a number of methods that you will be writing and a full implementation of the remove algorithm as discussed in the lectures. You do not need to do anything to the remove algorithm but you should look at it and compare it to the implementation in the slides - the remove method will not work until you finish the findMin and removeMin methods (which are required for the remove method as discussed in the lectures).

add method

The first method you need to implement in the project is an implementation of the recursive add method as discussed in the lecture. Follow the algorithm carefully as you add this method - there is a set of test cases in the test folder that you can use to confirm that this method is working. Note that the precondition is that that root is the root of a binary search tree - which means its either null (indicating an empty tree) or a tree that follows the ordering rules for binary search trees so your code can assume that the parameter follows the binary search tree rules.

The second method you need to write is the find method. This method returns true if the tree contains a particular value, false otherwise. Here's the method header - note that the precondition is as above, so it should return false for the empty tree (i.e. the null value) because nothing is ever in the empty tree:

/**
* Indicates if a value is in a binary search tree or not
* @param root the root of a binary search tree
* @param value the value to search for
* @precond root is the root of a binary search tree
* @return true if value is in the tree rooted at root, false otherwise
*/
public static boolean find(TreeNode root, String value)

findMin method

The third method you need to write is the findMin method. This method returns the minimum value stored in the tree. Here's the method header - note that the precondition here says that the tree cannot be empty, so the parameter passed to it cannot be null:

/**
* Finds the smallest value in a binary search tree
*
* @param root
* @precond root cannot be empty (i.e. root cannot be null)
* and root is the root of a binary search tree
* @return the smallest value in the tree
*/
public static String findMin(TreeNode root)removeMin method

The fourth method you need to write is the removeMin method. This method returns the root of a tree that has the smallest value removed from it. Here's the method header - note that the precondition here says that the tree cannot be empty, so the parameter passed to it cannot be null:

The remaining method you need to create is the inorderVist method for the binary tree. Here is the method header for the method - note the lack of a precondition - a null value for the tree should return an empty String. Note that in the previous project you wrote methods that were similar to this one - feel free to refer back to your previous project for this implementation:

/**
* Returns a comma-separated in-order list of the elements of the
* tree.
* @param root the root of a binary search tree
* @return a comma-separated string of the elements in the tree
* via an in-order visitation. If the tree is empty
* returns an empty String ""
*/
public static String inorderVisit(TreeNode root)SimpleSet implementation

Once you have all of the above methods working, the SimpleTreeSet implementation should now work. You can try the SetTesting.java program - this program exercises the various Set methods built into SimpleTreeSet - look at the code for both of these files and make sure you understand what is going on with it. You don't need to write any extra code here, just make sure that you understand why it works!

public class BinarySearchTreeMethods {

/**
* Add an element to its correct place in a binary search tree
* @param root the root node of a correctly built binary search tree
* @param value value to be inserted into the tree
* @precond root is the root of a binary search tree
* @return the root node of a binary search tree with value inserted into it
*/
public static TreeNode add(TreeNode root, String value) {
// TODO: Your code here

// TODO: The line below is only included so this shell will compile
// delete it and replace it with your own code
return null;
}

/**
* Indicates if a value is in a binary search tree or not
* @param root the root of a binary search tree
* @param value the value to search for
* @precond root is the root of a binary search tree
* @return true if value is in the tree rooted at root, false otherwise
*/
public static boolean find(TreeNode root, String value) {
// TODO: Your code here

// TODO: The line below is only included so this shell will compile
// delete it and replace it with your own code
return false;
}

/**
* Finds the smallest value in a binary search tree
*
* @param root
* @precond root cannot be empty (i.e. root cannot be null)
* and root is the root of a binary search tree
* @return the smallest value in the tree
*/
public static String findMin(TreeNode root) {
// TODO: Your code here

// TODO: The line below is only included so this shell will compile
// delete it and replace it with your own code
return "";
}

/**
* Remove the smallest value from a binary tree
*
* @param root - the tree to remove the value from
* @precond root cannot be empty (i.e. root cannot be null)
* and root is the root of a binary search tree
* @return the root of a binary search tree with the minimum value removed
*/
public static TreeNode removeMin(TreeNode root) {
// TODO: Your code here

// TODO: The line below is only included so this shell will compile
// delete it and replace it with your own code
return null;
}

/**
* Returns a comma-separated in-order list of the elements of the
* tree.
* @param root the root of a binary search tree
* @return a comma-separated string of the elements in the tree
* via an in-order visitation. If the tree is empty
* returns an empty String ""
*/
public static String inorderVisit(TreeNode root) {
// TODO: Your code here

// TODO: The line below is only included so this shell will compile
// delete it and replace it with your own code
return "";
}

/**
* Removes an arbitrary value from a binary search tree
* @param root the root of a binary search tree
* @param value the value to be removed
* @precond root cannot be empty (i.e. root cannot be null)
* and root is the root of a binary search tree
* and value is in the tree rooted by root
* @return the root of a tree with value removed from it
*/
public static TreeNode remove(TreeNode root, String value) {

if (root.getData().equals(value)) {
// root value equals the value we're looking for
if (root.hasRight()) {
if (!root.hasLeft()) {
// no left child - right tree is our new root
root = root.getRight();
}
else {
// both left and right child - most complex case
// find the minimum value from the right child
String min = findMin(root.getRight());
// remove the minimum node from the right child
TreeNode right = removeMin(root.getRight());
// replace the current node's value with the min value
root.setData(min);
// set the right child to our new right child with
// the minimum node removed
root.setRight(right);
}
}
else {
// no right child - left tree is our new root
root = root.getLeft();
}
}
else if (value.compareTo(root.getData()) < 0) {
// value is less than the root value, recursively remove from the left side
TreeNode left = root.getLeft();
left = remove(left, value);
root.setLeft(left);
}
else {
// value is greater than the root value, recursively remove from the right side
TreeNode right = root.getRight();
right = remove(right, value);
root.setRight(right);
}
// root has the root of our new tree, return it
return root;
}