public class BinarySearchTree { private int size; private BinaryTreeNode root; public BinarySearchTree() { this.root = null; this.size = 0; } public BinaryTreeNode getRoot() { return this.root; } public int getSize() { return this.size; } /** * Inserts the given integer and return nothing. It inserts this int such that the tree remains a BST. * @param data The integer to be inserted */ public void insert(int data) { // TODO } /** * Inserts the given integer and return nothing. It inserts this int such that the tree remains a BST. * @param data The integer to be inserted * @param curNode The current Node in the traversal */ private void insert(int data, BinaryTreeNode curNode) { // TODO } /** * Deletes a Node containing the given integer. If the Node has 2 children, replaces with the Node of the minimum * value in the right child of the node. If the data is not present, returns null. * @param data The integer to be removed * @return The Node containing the integer to remove or null if one is not found */ public BinaryTreeNode remove(int data) { // TODO return null; } /** * Deletes a Node containing the given integer. If the Node has 2 children, replaces with the Node of the maximum * value in the left child of the node. If the data is not present, returns null. * @param data The integer to be removed * @param curNode The current Node in the traversal * @return The Node containing the integer to remove or null if one is not found */ private BinaryTreeNode remove(int data, BinaryTreeNode curNode) { // TODO return null; } /** * A recursive method that starts at the left child of a parent and extracts the maximum from this child's tree. * @param curNode The current Node in the traversal * @return The minimum Node in the child's tree */ private BinaryTreeNode extractLeftMax(BinaryTreeNode curNode) { // TODO return null; } /** * Returns a Node containing the given integer or null if one is not found * @param data The integer to search for * @return A Node containing the given integer or null if one is not found */ public BinaryTreeNode search(int data) { // TODO return null; } /** * Returns a Node containing the given integer or null if one is not found * @param data The integer to search for * @param curNode The current Node in the traversal * @return A Node containing the given integer or null if one is not found */ private BinaryTreeNode search(int data, BinaryTreeNode curNode) { // TODO return null; } /** * Returns the pre-order traversal of this. The output must be in the form of: "x, x, x, x, x, x". Each number * except the last is followed by ", ". (i.e. for a tree with one node, the output would take the form: "x") * @return A String representation of the traversal */ public String getPreOrderStr() { // TODO return null; } /** * Returns the pre-order traversal of this. The output must be in the form of: "x, x, x, x, x, x". Each number * except the last is followed by ", ". (i.e. for a tree with one node, the output would take the form: "x") * @return A String representation of the traversal */ private String getPreOrderStr(BinaryTreeNode curNode) { // TODO return null; } /** * Returns the in-order traversal of this. The output must be in the form of: "x, x, x, x, x, x". Each number * except the last is followed by ", ". (i.e. for a tree with one node, the output would take the form: "x") * @return A String representation of the traversal */ public String getInOrderStr() { // TODO return null; } /** * Returns the in-order traversal of this. The output must be in the form of: "x, x, x, x, x, x". Each number * except the last is followed by ", ". (i.e. for a tree with one node, the output would take the form: "x") * @return A String representation of the traversal */ private String getInOrderStr(BinaryTreeNode curNode) { // TODO return null; } /** * Returns the post-order traversal of this. The output must be in the form of: "x, x, x, x, x, x". Each number * except the last is followed by ", ". (i.e. for a tree with one node, the output would take the form: "x") * @return A String representation of the traversal */ public String getPostOrderStr() { // TODO return null; } /** * Returns the post-order traversal of this. The output must be in the form of: "x, x, x, x, x, x". Each number * except the last is followed by ", ". (i.e. for a tree with one node, the output would take the form: "x") * @return A String representation of the traversal */ private String getPostOrderStr(BinaryTreeNode curNode) { // TODO return null; } } 

public class BinaryTreeNode { private int item; private BinaryTreeNode parent, left, right; public BinaryTreeNode(int item, BinaryTreeNode parent, BinaryTreeNode left, BinaryTreeNode right) { this.item = item; this.parent = parent; this.left = left; this.right = right; } public int getItem() { return item; } public BinaryTreeNode getParent() { return parent; } public BinaryTreeNode getLeft() { return left; } public BinaryTreeNode getRight() { return right; } public void setItem(int item) { this.item = item; } public void setParent(BinaryTreeNode parent) { this.parent = parent; } public void setLeft(BinaryTreeNode left) { this.left = left; } public void setRight(BinaryTreeNode right) { this.right = right; } }

import org.junit.jupiter.api.Test; import static org.junit.jupiter.api.Assertions.*; public class BinarySearchTreeTest { /* TODO: tests - Make sure you have 100% code coverage + This also means you should break your tests up by method - Make sure you test the full functionality of this class... think edge cases (bounds, exceptions, etc...) - Use JUnit (you will not receive points for testing if you do not use JUnit) */ } 

In this lab, you would be writing a BinarySearchTree and BinaryTreeNode. As a refresher: the nodes contained in the left subtree must be LESS THAN the parent and nodes contained in the right subtree must be GREATER the parent (for simplicity, you can assume all the integers are unique). Here is some code to help you get started: As you can see, you are writing a Tree for storing integers... You will be implementing the binary search tree: public class BinarySearchTree {BinaryTreeNoderoot;intsize; \} You have to implement the following functions in BinarySearchTree class: insert: Should take in the integer to be inserted and return nothing. It needs to insert this int such that the tree remains a BST (see the italicized text above). remove: If the node has 2 children, replace with the node of the maximum value in the left child of the node. If the value to be removed is not present, return null. search: Should take in the integer to be searched for and should return a reference to the node that contains the integer or null if one is not found. getPreOrderStr: Should return the pre-order String representation of the BinarySearchTree. i.e. the following tree should produce 3,1,0,2,5,4,6x (comma and space delimited with no comma and space at the end) getlnOrderStr: Should return the in-order String representation of the BinarySearchTree. i.e. the following tree should produce 0,1,2,3,4,5,6* (comma and space delimited with no comma and space at the end) getPostOrderStr: Should return the pre-order String representation of the BinarySearchTree. i.e. the following tree should produce 0,2,1,4,6,5,3n (comma and space delimited with no comma and space at the end) Test Cases Using Junit, please provide test cases that test the accuracy of your methods. You should test insert, remove, search, and your traversal functions. Remember, your tests should have 100% code coverage. If you are not close to 100% coverage within a few cases, we will deduct points. Grading Rubric - Attendance: 1pt - Test cases: 2 pts - insert: 2 pts - remove: 4pts - search: 2 pts - getPreOrderStr: 2 pts - getlnOrderStr: 2 pts - getPostOrderStr: 2 pts We will be looking to see if your methods follow the expected time complexities (all are O(n) ) (2)