Binary Search Tree (continued)

Assignment:

1. Add the following methods to your Binary Search Tree class from the previous Lab Assignment AB30.1.

   1. public Object find(Comparable target)
   2. private Object findHelper(TreeNode root, Comparable target)
   3. public void delete(Comparable target)
   4. private TreeNode deleteHelper(TreeNode node, Comparable target)
   
   

2. However, you are required to code the two-child case for deletion as a mirror image of the solution described in Section B.7 of the lesson. Change the deleteTargetNode method to deal with the two-child case as follows:

1. Position marker to access the node with the smallest value in the right subtree. This is the leftmost node in the right subtree.

2. Copy the contents of the left child of marker and set it as the current value.

3. Delete the smallest value from the left subtree. Reattach the left subtree to maintain an ordered tree.

3. Test your code and solve the following sequence of run output steps:

   1. Load the file from disk (file20.txt).
   2. Print the tree.
   3. Print the number of nodes in the tree.
   4. Search for Id values specified by your teacher. Print out the Id and Inv response in column form.
   5. Delete the Id values specified by your teacher.
   6. Print the tree again.
   7. Print the number of nodes in the tree.

Instructions:

1. Turn in your source code for the entire program and the run output described above.