Part 1: Counting Nodes (25 points) The public int count() method returns the number of nodes in the tree. You can implem

[answerhappygod]

Part 1: Counting Nodes (25 points)
The public int count() method returns the number of nodes in the
tree. You can implement this method recursively or iteratively
using a stack. If you implement the method recursively you will
need to create a private helper method. DO NOT CHANGE THE METHOD
SIGNATURE of the public count method. I wrote one JUnit test for
this method. You need to add at least 5 more JUnit tests. Make sure
that your code passes your JUnit tests.
Part 2: Level Order Traversal (40 points)
Implement the method public ArrayList<Integer>
levelOrder() which returns an ArrayList of integers that represent
the data in the binary search tree visiting in a level order
fashion. In a level order traversal you do the following. “Do the
work” in this case means to add the data from the node to the
ArrayList.
1. Visit the current node and “do the work” at the current
node
2. Visit the left child and right child and “do the work” on those
nodes
3. Visit the children of left child and the children of the right
child and “do the work” on
those nodes 4. ...
5. Continue until all nodes have been visited
results in 9 7 11 2 8 15
You will use a Queue to solve this problem. Here is the link for
the Java Documentation for a Queue. Note that the Queue in Java is
an interface and the LinkedList class is an implementing class.
Here is the link to the Java Documentation for Queues. As a
reminder the Queue is a First In First Out (FIFO) data structure
(i.e., the first element added to the queue is the first element
removed). Think about how this pattern will help you implement a
level order traversal.
I wrote one JUnit test for the traversal. Implement at least 5
more JUnit tests for your Level Order Traversal. Make sure that
your code passes your JUnit tests.
Part 3: Iterative Delete (35 points)
Implement the public void iterativeDelete(int d) method. This
method iteratively removes the node containing data equals to d
from the binary search tree if it
exists. The resulting tree must still be a binary search tree
containing all the nodes except the one you just deleted. You
should use the minimum successor strategy for removing a node with
two children (i.e., replace the data value in the node you want to
delete with the data of the minimum value in the right subtree, see
example below). This is the opposite of what we did in class. But
both strategies are equally valid.
STARTER CODE:
package treeDemo;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class BSTInt {
private static class BSTNode {
private int data;
private BSTNode
leftChild;
private BSTNode
rightChild;
public BSTNode(int data)
{
this.data
= data;
leftChild
= rightChild = null;
}

public String toString()
{
return
Integer.toString(data);
}
}

private BSTNode root;

public boolean contains(int d) {
return find(d)!=null;
}

private BSTNode find(int d) {
return
recursiveFind(root,d);
}

private BSTNode recursiveFind(BSTNode node, int
d) {
//base case, made it to the
end or I found it
if(node == null || d ==
node.data) {
return
node;
}
if(d < node.data) {
return
recursiveFind(node.leftChild,d);
}
else {
return
recursiveFind(node.rightChild,d);
}

}
//assumes node is not null
//used in deleting a node from the see with two
children
private BSTNode getMax(BSTNode node){
while(node.rightChild!= null)
{
node =
node.rightChild;
}
return node;
}

//equals method to compare if two BSTInts are
equal
//Computes a Preorder traversal of tree
//and confirms that the structure is the same
along
//with the values in the nodes
public boolean equals(Object o) {
BSTInt that =
(BSTInt)(o);
if(that.root == null
&& that.root == null) {
return
true;
}
else if(that.root == null ||
this.root == null) {
return
false;
}
Stack<BSTNode>
preOrderThis = new Stack<>();
Stack<BSTNode>
preOrderThat = new Stack<>();

preOrderThis.push(root);

preOrderThat.push(that.root);
while(!preOrderThis.isEmpty()
&& !preOrderThat.isEmpty()) {
BSTNode
thisNode = preOrderThis.pop();
BSTNode
thatNode = preOrderThat.pop();

if(thisNode.data != thatNode.data){

return false;
}
else
{

if(thisNode.leftChild!=null)


preOrderThis.push(thisNode.leftChild);

if(thisNode.rightChild!=null)


preOrderThis.push(thisNode.rightChild);

if(thatNode.leftChild!=null)


preOrderThat.push(thatNode.leftChild);

if(thatNode.rightChild!=null)


preOrderThat.push(thatNode.rightChild);
}
}
return preOrderThis.isEmpty()
&& preOrderThat.isEmpty();
}

//sum all the nodes in a tree
public int sum() {
return sumRec(root);
}

private int sumRec(BSTNode current) {
if(current == null) {
return
0;
}
else {
return
current.data +


sumRec(current.leftChild)+


sumRec(current.rightChild);
}
}

//computed using the sum.
//not the smartest hashCode method
public int hashCode() {
return sum();
}

//to String method so that the tree can
be
//printed in a readable format
public String toString() {
return
recursiveToString(root,"");

}

//helper method so the tree can be printed
//in a readable format
private String recursiveToString(BSTNode node,
String indent) {

if(node == null) {return
"";}
else {

return


recursiveToString(node.rightChild,indent + "
")+

"\n" + indent
+node.data +


recursiveToString(node.leftChild,indent + "
");
}
}

/*
* This is where your implementation
starts
*/

//Feel free to adda private recursive helper
method
public int count() {
return -1;
}

public ArrayList<Integer> levelOrder(){
ArrayList<Integer> travOrder =
new ArrayList<>();
if(root!=null) {
Queue<BSTNode>
queue = new LinkedList<>();
queue.add(root);
//and... you will need a
while loop
}
return travOrder;
}

//This method should iteratively delete the node
containing d from the tree
public void iterativeDelete(int d) {
//feel free to change these
variables
//they are just a hint to how you can
think about this problem iteratively
BSTNode current = root;
BSTNode parent = null;

}
public static void main(String[] args)
{
//You can use this method for
basic testing
//But I recommend writing any
code you test here as a JUnit test


}
}