6. Tree Nodes 1-5

6_1. Construct a BST on paper using the following values (5, 9, 3, 7 ,8,1,6, 2, 4). How many leaves are there? How many nodes have two children? How many nodes have only one child? How many iterations are required to ascertain that 12 is not in the BST? 
Construct the tree using the simulation provided at..
http://www.cs.jhu.edu/~goodrich/dsa/trees/btree.html 
Does this simulation confirm your paper tree diagram?


6.1 In my BST I have four leaves, three nodes with two children, and two nodes with only one child. Just one iteration is needed to find that 12 is not in the BST. You go from 5 to 9 which has no right node, so you know nothing is greater than 9.


6_2. Draw a BST for the following sequence of Strings {carter, reagan, bush, clinton, bush. }Create a new BST instance on the BlueJ workbench, then use the add() method to add the sequence of Strings. Inspect the BST object on the workbench to verify that the tree has the shape that you drew. 


6.2 Worked, and verified that it's the same shape.


6_3. Modify add() so that duplicates are not inserted into the tree (only one bush allowed). Test your code with the sequence of Strings. Does the new BST contain only 4 Objects?


6.3.              if (((Comparable)newNode.getValue()).compareTo(T.getValue())==0)
            {
                System.out.println("Please only insert a value once. No copies will be tolerated.");
            }

I added that method to the while loop in add(). Daly your getting easier with your homework, I like this.

6_4. Clear the BlueJ workbench of all objects and create 5 new TreeNode Objects using the series of Strings {Carter, reagan, bush, clinton, bush. }.For the first Object, the Name of Instance should be Carter, and the Object initValue should be "Carter", the two TreeNode references should be null. Continue in the same way for the next 4 Objects and Strings
Now create a new BST instance on the workbench and add the TreeNode Objects from the workbench in the order {Carter, reagan, bush, clinton, bush. }.
You should find that the program crashes with a ClassCastException error, when an attempt is made to add the second Object (reagan).
Explain precisely why this error occurs.
What could be done to avoid this error?


6.4. I believe it's because we don't have the node T casted with the (Comparable) phrase. That would be the only thing that I believe would explain the first node (which is casted with (Comparable)) being taken by the system, and not T. To fix it we should cast the second to (Comparable).

6_5. Implement the find() method using the following header.

//returns the reference to target in the BST, if found, otherwise returns null
public Object find(Object target)

The structure of find() is quite similar to that of method add(). You should look carefully at add(), and perhaps even copy the code for add to the body of find() and edit.

6.5. 

//returns the reference to target in the BST, if found, otherwise returns null
public Object find(Object target)
{
    TreeNode newNode = new TreeNode(target.toString(),null,null);
    if(root==null)//bst is empty, make root reference node referenced by newNode
    {
        return null;
    }//if


    else//search for place to insert node referenced by newNode
    {
        TreeNode T=root;//T is a traversing TreeNode reference (pointer)
        TreeNode follow=null;//follows one node behind T


        while(T!=null)
        {
            if (((Comparable)newNode.getValue()).compareTo(T.getValue())==0)
            {
                return T;
            }
            follow=T;
            if (((Comparable)newNode.getValue()).compareTo(T.getValue())>0)
            {//the value in node referenced by newNode >= 
              //value in node referenced by T (go right)
                T=T.getRight();
            }//if
            else
            {//go left
                T=T.getLeft();
            }//else
        }//while


       return null;
    }//else
}