Part 1: Insert nodes into a tree We provided a file BinaryTree.java that defines a class for a binary tree and some methods. The method insertNode() inserts a node in the leftmost available free spot. That is, if the method is called in the following sequence: insertNode(50), insertNode(2), insertNode(34), insertNode(19), insertNode(6), then the tree will look like:

50

2 34

19 6

And, if we call insertNode(22), the tree will look like:

50

2 34

16 6 22

Notice that the breadth-first traversal order of the resulting tree is the order in which nodes were inserted. Implement this method using the fields in the constructor. Notice that there is a LinkedList called nodesThatNeedChildren. This List should contain the TreeNodes who are missing 1 or 2 children. Your insert method will use nodesThatNeedChildren to know which TreeNode to add a child to. For example, in the first tree above, nodesThatNeedChildren = [TreeNode(34),TreeNode(19),TreeNode(6)] and in the second tree, nodesThatNeedChildren = [TreeNode(34),TreeNode(19),TreeNode(6),TreeNode(22)].

Reference Code:

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;

}

}

}