1. Download the following class source files:

- BTNode.java

- mainExecutable.java

- SimpleBinaryTree.java (Note: the only class you need to implement!)

2. In Eclipse, create a new Java project, and import the three files.

3. In SimpleBinaryTree.java, fill in the code for method containsObject() that will determine if an object is in the tree. You may assume that all stored objects are integers and therefore can use Integer.parseInt() on the object for comparative purposes. Analyze method addObject() to understand what is meant by this. This method should be done iteratively (with loops).

4. A leaf node of a binary tree is a node that has no children (.getLeft() and .getRight() are both null). In SimpleBinaryTree.java, fill in the code for method countLN() that will recursively check EVERY node in the tree to see if its a leaf node. Hint: You will have 2 terminating conditions 1:you found a leaf node 2: trav is null

5. The tree that is being created in memory is being created with the following values in the following order in mainExecutable.java: 10, 106, 1, -10, 64, 65, 85,-20, 200, 9, 63. Build this tree yourself by hand on paper. Count up the leaf nodes.

6. Compile and run the program. Make sure it works correctly. Is the outputted leaf count the same as the one you counted from your tree?

public class SimpleBinaryTree {

private BTNode root;

public SimpleBinaryTree()

{

root = null;

}

public void addObject(Object obj)

{

/*This method builds the tree for us*/

//If the root is null, simply set root to obj

if(root == null)

{

root = new BTNode(obj);

}else

{

//assume value is an integer

int value1 = Integer.parseInt((String)obj);

//Create a traverse pointer

BTNode trav = root;

while(true)

{

//get the value of the object pointed to by trav

int value2 = Integer.parseInt((String)trav.getObject());

//if the value of the current node has a value greater than the obj go left

if(value1

if(trav.getLeft() == null)

{

//if left is null, create the new node and set it there

trav.setLeft(new BTNode(obj));

return;

}else

{

//else have trav go left;

trav = trav.getLeft();

}

else

if(trav.getRight() == null)

{

//if right is null, create the new node and set it there

trav.setRight(new BTNode(obj));

return;

}else

{

//else have trav go right;

trav = trav.getRight();

}

}

}

}

public int countLeafNodes()

{

/* A leaf node is defined as having no children (.getRight and .getLeft are null)

*/

//Use a recursive function countLN that traverses all nodes and counts them

return countLN(root);

}

private int countLN(BTNode trav)

{

/**************This function must be recursive********************/

//Terminating cases

if(trav==null)

return 0;

if((trav.getLeft()==null)&&(trav.getRight()==null))

{

//child node!

return 1;

}

int count = 0;

//FILL IN CODE HERE

return count;

}

public boolean containsObject(Object obj)

{

BTNode trav = root;

int value1 = Integer.parseInt((String)obj);

//FILL IN CODE HERE

return false;

}

}

public class mainExecutable {

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

SimpleBinaryTree sbt = new SimpleBinaryTree();

sbt.addObject(new String("10"));

sbt.addObject(new String("106"));

sbt.addObject(new String("1"));

sbt.addObject(new String("-10"));

sbt.addObject(new String("64"));

sbt.addObject(new String("65"));

sbt.addObject(new String("85"));

sbt.addObject(new String("-20"));

sbt.addObject(new String("200"));

sbt.addObject(new String("9"));

sbt.addObject(new String("63"));

if(sbt.containsObject(new String("85")))

System.out.println("Correct, it does contain 85");

else

System.out.println("Incorrect, it does contain 85");

if(sbt.containsObject(new String("87")))

System.out.println("Incorrect, it does not contain 87");

else

System.out.println("Correct, it does not contain 87");

System.out.println("Leaf count is: "+sbt.countLeafNodes());

}

}

public class SimpleBinaryTree {

private BTNode root;

public SimpleBinaryTree()

{

root = null;

}

public void addObject(Object obj)

{

/*This method builds the tree for us*/

//If the root is null, simply set root to obj

if(root == null)

{

root = new BTNode(obj);

}else

{

//assume value is an integer

int value1 = Integer.parseInt((String)obj);

//Create a traverse pointer

BTNode trav = root;

while(true)

{

//get the value of the object pointed to by trav

int value2 = Integer.parseInt((String)trav.getObject());

//if the value of the current node has a value greater than the obj go left

if(value1

if(trav.getLeft() == null)

{

//if left is null, create the new node and set it there

trav.setLeft(new BTNode(obj));

return;

}else

{

//else have trav go left;

trav = trav.getLeft();

}

else

if(trav.getRight() == null)

{

//if right is null, create the new node and set it there

trav.setRight(new BTNode(obj));

return;

}else

{

//else have trav go right;

trav = trav.getRight();

}

}

}

}

public int countLeafNodes()

{

/* A leaf node is defined as having no children (.getRight and .getLeft are null)

*/

//Use a recursive function countLN that traverses all nodes and counts them

return countLN(root);

}

private int countLN(BTNode trav)

{

/**************This function must be recursive********************/

//Terminating cases

if(trav==null)

return 0;

if((trav.getLeft()==null)&&(trav.getRight()==null))

{

//child node!

return 1;

}

int count = 0;

//FILL IN CODE HERE

return count;

}

public boolean containsObject(Object obj)

{

BTNode trav = root;

int value1 = Integer.parseInt((String)obj);

//FILL IN CODE HERE

return false;

}

}