Part 2: reduceAtDepth Write a method that returns the reduced value of the nodes at a given depth. Here, "reduced" means the same as what ReduceFunction defines in HW5, that is, start with ReduceFunction.initialValue() and combine each element to the total value using ReduceFunction.combine(). The depth is given as a parameter. If the depth of the tree is actually less than the given height, then return ReduceFunction.initialValue(). Your method must have a running time in O(N), where N is the number of nodes in the tree. In BinaryTree.java, complete reduceAtDepth() and reduceAtDepthRecurisve(). reduceAtDepthRecurisve() must use recursion and reduceAtDepth() must be iterative (use a loop). Notice that the generic data types of reduceAtDepthRecurisve() makes the input and output type to be the same type, T. This is just to make the recursion easier. Notice that there is a signature for a private helper method reduceAtDepthHelper. It has more arguments to facilitate the recursive calls. Example If the tree looks like

50

2 34

19 6 (branches from 2 not 34) And the given ReduceFunction is plus (+), then reduceAtDepth(0) is 50, reduceAtDepth(1) is 36 and reduceAtDepth(2) is 25. Testing There is one test, sumOfDepthTest, in BinaryTreeTest.java. You must write additional test cases to ensure your code is correct. Your methods will be graded on several additional hidden tests. Some examples of things to test, an empty tree, a tree with only one node, different tree shapes etc. HINT 1: The provided tests include only one ReduceFunction implementation, IntegerSum. The hidden tests will use other ReduceFunctions, so test your code with other ReduceFunctions that you define. HINT 2: The provided tests include only BinaryTree. The hidden tests will use other types for BinaryTree, so test your code with other types, such as BinaryTree. To write a new test case, we recommend that you copy/paste an existing one and change the name of the test method. Then draw your test tree on paper so you know what order to insert nodes using insertNode and what your assertions' expected values are.

Reference Code:

ReduceFunction.java

package iterators;

// Interface for classes to define the functions needed for Reduce.

public interface ReduceFunction {

/* Take the accumulated value soFar and combine it with x

to return a new accumulated value

*/

public OutT combine(OutT soFar, InT x);

/* Return the initial accumulated value */

public OutT initialValue();

}

Binary Tree:

package binaryTree;

import iterators.Predicate;

import iterators.ReduceFunction;

import java.util.*;

public class BinaryTree {

// the root of the tree

private TreeNode root;

// the queue of TreeNodes in the tree that have 0 or 1 children

private final List> nodesThatNeedChildren;

// number of TreeNodes in the tree

public int size;

public BinaryTree() {

root = null;

nodesThatNeedChildren = new LinkedList<>();

size = 0;

}

/*

Insert the element d into the BinaryTree at the

"next available location" starting with the left

*/

public void insertNode(T d) {

//PART 1 HERE

}

/* Takes a depth n and a ReduceFunction f

and returns the "combined value" of all elements in the tree at depth n,

where depth=0 is the root.

"combined" means the result of starting with f.initialValue

and "concatentation or combination" each element using f.combine

Requirement: must use a loop

Note on Java syntax: The in front of the method introduces a generic

type name OutT for use only by this method. This is helpful when the generic

type doesn't hold much meaning for the whole class but is meaningful for a

single method.

*/

public OutT reduceAtDepth(int depth, ReduceFunction f) {

//PART 2 HERE

return null;

}

/*Takes a depth n and a ReduceFunction f

and returns the "combined value" of all elements in the tree at depth n,

where depth=0 is the root.

"combined" means the result of starting with f.initialValue

and "concatentation or combination" each element using f.combine

NOTE that the "in" generic type and "out" generic type are the same type.

This makes the recurision a easier.

Requirement: must use a recursive.

*/

public T reduceAtDepthRecursive(int n, ReduceFunction f) {

return null;

// replace the above line with the following line, with arguments

// filled in

// return combineValuesHelper(______, ____, ____, _____);

}

private T reduceAtDepthHelper(int depth, TreeNode node, ReduceFunction f, T sum){

//PART 2 HERE

return null;

}

/* Takes a Predicate p and returns the list of all elements

for which p.check is true. The elements must be returned in

"in order" traversal order.

Requirement: must use a loop

*/

public List selectIterative(Predicate p) {

//PART 4

return null;

}

/* Takes a Predicate p and returns the list of all elements

for which p.check is true. The elements must be returned in

"in order" traversal order.

Requirement: must be recursive

*/

/*

Requirement: must be recursive

*/

public List selectRecursive(Predicate p) {

return selectRecursiveHelper(p, root);

}

private List selectRecursiveHelper(Predicate p, TreeNode node){

if(node == null) {

return null;

}

List res = new LinkedList();

if(p.check(node.data)) {

res.add(node.data);

}

if(node.left != null) {

List wantedNodes = (selectRecursiveHelper(p, node.left));

for(int i = 0; i < wantedNodes.size(); i++) {

res.add(wantedNodes.get(i));

}

}

if(node.right != null) {

List wantedNodes = (selectRecursiveHelper(p, node.right));

for(int i = 0; i < wantedNodes.size(); i++) {

res.add(wantedNodes.get(i));

}

}

return res;

}

//////////////// Dont edit after here //////////////////////

public void printTree() {

Object[] nodeArray = this.toArray();

for (int i = 0; i < nodeArray.length; i++) {

System.out.println(nodeArray[i]);

}

}

public void displayTree()

{

Stack globalStack = new Stack();

globalStack.push(root);

int emptyLeaf = 32;

boolean isRowEmpty = false;

System.out.println("****..................................................................................................................................****");

while(isRowEmpty==false)

{

Stack localStack = new Stack();

isRowEmpty = true;

for(int j=0; j

System.out.print(" ");

while(globalStack.isEmpty()==false)

{

TreeNode temp = (TreeNode) globalStack.pop();

if(temp != null)

{

System.out.print(temp.data);

localStack.push(temp.left);

localStack.push(temp.right);

if(temp.left != null ||temp.right != null)

isRowEmpty = false;

}

else

{

System.out.print("--");

localStack.push(null);

localStack.push(null);

}

for(int j=0; j

System.out.print(" ");

}

System.out.println();

emptyLeaf /= 2;

while(localStack.isEmpty()==false)

globalStack.push( localStack.pop() );

}

System.out.println("****..................................................................................................................................****");

}

public Object[] toArray() {

Object[] r = new Object[size];

if (root == null) {

return r;

}

// traverse the tree to visit all nodes,

// adding them to r

List frontier = new LinkedList<>();

frontier.add(root);

int soFar = 0;

while (frontier.size() > 0) {

TreeNode v = (TreeNode) frontier.get(0);

r[soFar] = v.data;

soFar++;

if (v.left != null) {

frontier.add(v.left);

}

if (v.right != null) {

frontier.add(v.right);

}

frontier.remove(0);

}

return r;

}

private static class TreeNode {

public T data;

public TreeNode left;

public TreeNode right;

public TreeNode(T d) {

data = d;

left = null;

right = null;

}

}

}