CPE 103 

Before you write any code, read the directions and write a test plan.  Draw the tree you will create, the data to be input (in order), and show the exact program output you expect.

Implement the test plan you wrote as JUnit test to demonstrate that all six methods perform correctly.   Compile your test and run it.  It should compile without error, and when executed it should report that the tests fail.  (Your test of the print method won't have any asserts; it will rely on human inspection of the output to verify correctness.)

We will be enhancing Weiss's BinarySearchTree implementation.
Download:

• DuplicateItemException.java
• BinaryNode.java
• BinarySearchTree.java
• ItemNotFoundException.java

In the class header comment for BinarySearchTree include separate @author tags for each student.

Implement the following six methods in your class.  The search() and traverse() methods must be implemented recursively. search() must not call find().

   /** See if the tree contains a given item.
    * @param target the item to search for
    * @return true if the item is in the tree
    */
   public boolean contains(AnyType target)

    /** Recursively search the tree for the target */
   private boolean search(BinaryNode<AnyType> curr, AnyType target)

   /** Show an ordered list of the items in the tree,
    * one item per line.     */
   public void list()
        
   /** Recursive in-order traversal of the tree, printing each node */
   private void traverseInOrder(BinaryNode<AnyType> curr)

   /** Print a formatted display of the tree.  */
   public void print()

   /** Recursive pre-order traversal of the tree, printing each node
    * indented an amount corresponding to its level in the tree.
    */
   private void traversePreOrder(BinaryNode<AnyType> curr, int indent)
        

The formatted display uses indenting to show nodes on the same level at a consistent level of indentation, and periods where no child exists.
For example, the tree in this diagram  would print like this:

   E
      D
         .
         .
      N
         K
            F
               .
               H
                  .
                  .
            L
               .
               .
         S
            .
            W
               .
               .