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 the following Id values:

      100  184  12345  15320  16000  19967  23456

      Print out the Id and Inv response in column form.

   5. Delete the following Id values:

      18618  184  150  20000  14088  1400  18465

   6. Print the tree again.

   7. Print the number of nodes in the tree.

Instructions:

1. Submit your source code for the entire program and attached the run output described above.