JAVA
Binary Search Tree Implementation Create a class called BinaryTree. Because elements need to be stored in a sorted manner, you can assume that any elements added to the tree implement the Comparable class with the appropriate generic type. Including Comparable instead of simply Comparable ensures that the generic can be any subclass of a class implementing the Comparable interface. public class BinaryTree > Within the BinaryTree class, create a private class that will represent a node in the tree. private class BinaryNode Each node should contain the data object (value) that you would like to store and references to the right and left child nodes. private E value; private BinaryNode right; private BinaryNode left; Add a constructor to BinaryNode that will store that node's data. public BinaryNode(E valueIn) { value = valueIn; } At the top of your BinaryTree class, add the following instance variables to hold the root node of the tree (a BinaryNode) and the size of the tree: private int size = 0; private BinaryNode root = null; In order to add elements to a tree, you can create a support method that adds a new node to a specified parent node. The method will return false if the value is equal to an element already present in the tree based on natural ordering (the compareTo method of the value). private boolean addToParent(BinaryNode parentNode, BinaryNode addNode) First, create an integer that will compare the parent node's value to the child node's value. Also create a boolean to represent whether the node was added: int compare = parentNode.value.compareTo(addNode.value); boolean wasAdded = false; If the parent is greater than the child value, then the child will be added to the left node. This can only be performed if the left node of the parent is null. Otherwise, the method will need to be invoked recursively with the left node of the parent: Data Structures Binary Search Tree Data Structures | Stack 2 if (compare > 0) { // if parent has no left node, add new node as left if (parentNode.left == null) { parentNode.left = __________; wasAdded = true; } else { // otherwise, add to parentNode's left (recursive) wasAdded = addToParent(parentNode.__________, addNode); } } Create a similar statement to add to the right node of the parent if the value of the added node's value is greater: else if (compare < 0) { // if parent has no right node, add new node as right if (parentNode.right == null) { parentNode.__________ = addNode; wasAdded = true; } else { // otherwise, add to parentNode's right (recursive) wasAdded = addToParent(parentNode.__________, addNode); } } Now return whether the element was added (false only if the parent and child were equal in value): return wasAdded; Create a method that users will call to add a value to the tree. public boolean add(E value) { } First, create a node to reference the new element: BinaryNode node = new BinaryNode(value); boolean wasAdded = true; If the tree is empty (the root node is null), then set the root to the new node: if (root == null) { root = node; } Otherwise, add the value to the tree using the root as the parent: else { wasAdded = __________(root, node); } Data Structures Binary Search Tree Data Structures | Stack 3 If the element was added to the tree, then increment the size of the tree by 1 and return whether the element was added: if (wasAdded) { size++; } return wasAdded; Create a main method to test your program. You can add any objects to your tree as long as they implement the Comparable interface. Add a breakpoint to the first add operation of the code: Run your program in debug mode and open a viewer by pulling the variable tree out of the Workbench. Use the step in button to enter the add method. The next value is 4. The value of 4 is greater than 3, but both children of the root node are occupied so the value will be added to the left child of 5. When you step into the addToParent method, open a viewer on parentNode. The parent node (in this case 5, on the second call to addToParent) will be marked along with the node to be added. When the node is added to the tree, you will see an animation of the add node being connected to the current parent. Try the same with adding the value 6. The parent node will again become 5, and 6 will be added to the right-hand side. Data Structures Binary Search Tree Data Structures | Stack 4 Add the following code to the end of your main method. Where will the following elements be added in the tree? Use the viewers in debug mode to verify your answer. tree.add(8); tree.add(1); Create a method that will remove a value from the tree and return true if that element was found: public boolean remove(E value) { } If the tree is empty (the root is null), then return false: if (root == null) { return false; } If the node to remove is the root, then you'll have to set a new root node. The code below performs the following operations: o If the left child is null, then make the right right child the root. o If the right child is null, then make the left right child the root. o Otherwise (if neither the left child nor the right child are null), set the left node to the root and then add the right node to the left node using the addToParent method. Recall that the addtoParent method will add to the most appropriate spot in the tree. if (root.value.compareTo(value) == 0) { if (root.left == null) { root = root.right; } else if (root.right == null) { root = root.left; } else { BinaryNode formerRight = root.right; root = root.left; addToParent(root, formerRight); } size--; return true; } If the node to remove is not the root, then another recursive method must be invoked to find the element in the tree and remove it. Add the following code to remove: return removeSubNode(root, value); The removeSubNode method will remove a node was not determined to be the root, or work its way down the branches of the tree to remove the appropriate node. Data Structures Binary Search Tree Data Structures | Stack 5 private boolean removeSubNode(BinaryNode parent, E value) { } First, create a variable to compare the parent node's value and the value to be removed: int compareParent = parent.value.compareTo(value); Now, pick whether the value to be removed is on the right or left of the parent: BinaryNode branch = (compareParent > 0)? parent.___ : parent.___; If that branch is null, then the value doesn't exist in the tree: if (branch == null) { return false; } If the value is equal to the value in the current branch, then the selected node can be deleted. The following steps are very similar to deleting the root. Because the replacement node is stored locally, it will have to be added back to the parent: if (branch.value.compareTo(value) == 0) { BinaryNode replacement; if (branch.left == null) { replacement = branch.right; } else if (branch.right == null) { replacement = branch.left; } else { BinaryNode formerRight = branch.right; replacement = branch.left; addToParent(replacement, formerRight); } if (compareParent > 0) { parent.__________ = replacement; } else { parent.__________ = replacement; } size--; return true; } If the value could still exist in the tree but is not the current branch, then invoke the method recursively with the branch node: return removeSubNode(branch, value); Data Structures Binary Search Tree Data Structures | Stack 6 Add methods to return the size of the tree and to make the tree empty. Because Java performs automatic garbage collection, you can set the root to null and all child nodes will be removed as well. public int size() { return size; } public void clear() { root = null; size = __; } In your main method, create the following tree: How many calls are made to the removeSubNode method to delete the element 7? What can you say about the efficiency of the remove method as it relates to the height of the tree? Remove the element with value 1 and step through the debugger during that step. When you step into the removeSubNode method, open a viewer on parent. You should see the branch variable moving through the tree until the value is found. When the value is found, a replacement for the node is determined and the tree is updated. Make sure that you are able to view the following animations. What does the tree look like after the elements 6 and 1 are deleted?
Submit the completed BinaryTree class implementation
