For this project you will write a program which exercises the Binary Search Tree

Question

For this project you will write a program which exercises the Binary Search Tree data structure, the BinarySearchTree class. Your program will create an empty Binary Search Tree of integers and read in a sequence of commands to exercise the Binary Search Tree. Design 1. Download the file BinarySearchTree.java containing most of the implementation of the Binary Search tree class. You cannot add data members to or modify the data member (root) of the Binary Search tree class. You cannot modify the nested private class Node of the Binary Search tree class. You cannot modify the Binary Search tree class constructor and the makeEmpty, isEmpty, contains, findMin, findMax, iterator, and inOrderTraversal methods. 2. You will write the code for the insert method using iteration to insert a value into the Binary Search Tree. A duplicate value will not be inserted into the Binary Search Tree. If needed, you can write additional methods to help in your implementation of the insert method but they must be defined as private. 3. You will write the code for the remove method using iteration to remove the value from the Binary Search Tree if the value is in the Binary Search Tree. If needed, you can write additional methods to help in your implementation of the remove method but they must be defined as private. Page 2 of 5 4. You will write the code for the printTree method for the Binary Search Tree. The printTree method will print the values in the binary search tree in a tree like structure. If needed, you can write additional methods to help in your implementation of the printTree method but they must be defined as private. Here is an example of a binary search tree to illustrate how your tree like structure can appear. The binary search tree is initially empty and the integers are inserted in the following order: 45, 67, 12, 34, 25, 39, 79, 53, 9. Here is the binary search tree in tree form as drawn by hand. Your program would not be able to print the tree in this way. Here is one way your program can print the binary search tree in tree form with the root of the tree on the top line. 45 12 67 9 34 53 79 25 39

Explanation / Answer

class BinarySearchTree { public static Node root; public BinarySearchTree(){ this.root = null; } public boolean find(int id){ Node current = root; while(current!=null){ if(current.data==id){ return true; }else if(current.data>id){ current = current.left; }else{ current = current.right; } } return false; } public boolean delete(int id){ Node parent = root; Node current = root; boolean isLeftChild = false; while(current.data!=id){ parent = current; if(current.data>id){ isLeftChild = true; current = current.left; }else{ isLeftChild = false; current = current.right; } if(current ==null){ return false; } } //if i am here that means we have found the node //Case 1: if node to be deleted has no children if(current.left==null && current.right==null){ if(current==root){ root = null; } if(isLeftChild ==true){ parent.left = null; }else{ parent.right = null; } } //Case 2 : if node to be deleted has only one child else if(current.right==null){ if(current==root){ root = current.left; }else if(isLeftChild){ parent.left = current.left; }else{ parent.right = current.left; } } else if(current.left==null){ if(current==root){ root = current.right; }else if(isLeftChild){ parent.left = current.right; }else{ parent.right = current.right; } }else if(current.left!=null && current.right!=null){ //now we have found the minimum element in the right sub tree Node successor = getSuccessor(current); if(current==root){ root = successor; }else if(isLeftChild){ parent.left = successor; }else{ parent.right = successor; } successor.left = current.left; } return true; } public Node getSuccessor(Node deleleNode){ Node successsor =null; Node successsorParent =null; Node current = deleleNode.right; while(current!=null){ successsorParent = successsor; successsor = current; current = current.left; } //check if successor has the right child, it cannot have left child for sure // if it does have the right child, add it to the left of successorParent. // successsorParent if(successsor!=deleleNode.right){ successsorParent.left = successsor.right; successsor.right = deleleNode.right; } return successsor; } public void insert(int id){ Node newNode = new Node(id); if(root==null){ root = newNode; return; } Node current = root; Node parent = null; while(true){ parent = current; if(id

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.