//TestingAssignment3

public class TestingAssignment3 {

// creating the tree // 5 // / \ // 2 6 // / \ // 1 4 // / \ // 8 -2 public static BinaryTree createTree() { BTNode node8 = new BTNode(8); BTNode nodeNegative2 = new BTNode(-2); BTNode node4 = new BTNode(4, node8, nodeNegative2, null);

BTNode node1 = new BTNode(1); BTNode node2 = new BTNode(2, node1, node4, null);

BTNode node6 = new BTNode(6); BTNode node5 = new BTNode(5, node2, node6, null);

return new BinaryTree(node5); }

public static void testNumberOfLeaves() { BinaryTree tree = createTree(); if (tree.numberOfLeaves() == 4) System.out.println("numberOfLeaves OK"); else System.out.println("numberOfLeaves ERROR"); }

public static void testCountDepthK() { BinaryTree tree = createTree(); if (tree.countDepthK(0) == 1 && tree.countDepthK(2) == 2 && tree.countDepthK(5) == 0) System.out.println("countDepthK OK"); else System.out.println("countDepthK ERROR"); }

public static void testMap() { BinaryTree tree = createTree(); tree.map(x -> x * 2); BTNode root = tree.getRoot(); BTNode ll = tree.getRoot().getLeftChild().getLeftChild(); BTNode lr = tree.getRoot().getLeftChild().getRightChild(); BTNode r = tree.getRoot().getRightChild();

if (root.getData() == 10 && ll.getData() == 2 && lr.getData() == 8 && r.getData() == 12) System.out.println("map OK"); else System.out.println("map ERROR"); }

public static void testPathFromRoot() { BinaryTree tree = createTree(); BTNode negativeTwo = tree.getRoot().getLeftChild().getRightChild().getRightChild(); List> l = tree.pathFromRoot(negativeTwo); if (l.size() == 4 && l.get(0) == tree.getRoot() && l.get(1) == tree.getRoot().getLeftChild() && l.get(3) == negativeTwo) System.out.println("pathFromRoot OK"); else System.out.println("pathFromRoot ERROR"); }

public static void testDistance() { BinaryTree tree = createTree(); BTNode five = tree.getRoot(); BTNode negativeTwo = five.getLeftChild().getRightChild().getRightChild(); BTNode six = five.getRightChild();

BTNode eleven = new BTNode(11);

try { tree.distance(five, eleven); } catch (IllegalArgumentException e) { } catch (Exception e) { System.out.println("distance: wrong exception"); return; }

if (tree.distance(five, six) == 1 && tree.distance(negativeTwo, five) == 3 && tree.distance(negativeTwo, six) == 4) System.out.println("distance OK"); else System.out.println("distance ERROR"); }

public static void testPreOrderIterator() { BinaryTree tree = createTree(); // 5 // / \ // 2 6 // / \ // 1 4 // / \ // 8 -2 Iterator it = tree.preOrderIterator(); // [5,2,1,4,8,-2,6] int firstFour[] = {5,2,1,4}; boolean flag = true; for (int i = 0; i six = tree.getRoot().getRightChild(); six.setLeftChild(new BTNode(100)); six.setRightChild(new BTNode(-50)); // 5 // / \ // 2 6 // / \ / \ // 1 4 100 -50 // / \ // 8 -2

// it has [8,-2,6,100,-50] left int last5[] = {8,-2,6,100,-50}; for (int i = 0; i

if (flag) System.out.println("preOrderIterator OK"); else System.out.println("preOrderIterator ERROR"); }

public static void main(String[] args) { testNumberOfLeaves(); testCountDepthK(); testMap(); testPathFromRoot(); testDistance(); testPreOrderIterator(); }

}

//BINARY TREE

//BTNode

You need to implement the following classes: - binarytree.BinaryTree - binarytree.BTNode Note that all files must be under the correct package (folder). You may add more classes to your solution if necessary. Make sure your zip file can be unzipped using the command "unzip assignmen3.zip" in CSIL. The zip file needs to contain exactly one folder: src. In the src folder there must be one folder/package: binarytree. The binarytree folder needs to contain the following files (and any additional files if needed): - src/binarytree/BTNode.java - src/binarytree/BinaryTree.java References: You may use textbooks, wiki, stack overflow, geeksforgeeks, etc. If you do, specify the references in comments. Readability: Your code should be readable using the standard Java conventions. Add comments wherever is necessary. If needed, write helper functions or add classes to improve readability. Compilation: Your code MUST compile in CSIL using javac. Make sure that your code compiles without warnings/errors. If the code does not compile in CSIL the grade on that part will be 0 (zero). Even if you can't solve a problem completely, make sure it compiles. The assignment will be graded mostly automatically, with some exceptions. Do not add main() to your solutions. The main() method will be in the test files. Warnings: Warnings during compilation will reduce points. More importantly, they indicate that something is probably wrong with the code. Testing: Test your code. Examples of tests are included. Your code will be tested using the provided tests as well as additional tests. You should create more tests to check your solution. Write the following methods in the class BinaryTree. a) [10 points] int numberOfLeaves() The method returns the number of leaves in the tree. b) [15 points] int countDepthK(int k) The method returns the number of nodes in the tree with depth=k. If k is greated than the depth of the tree, the method returns 0 . c) [15 points] void map(Function super T, ? extends T> mapper) The method gets a mapper, and for each node in the tree applies it to the node.data. In order to apply the mapper on the data in a node you may use the line node.setData(mapper.apply(node.getData())) For the API see https://docs.oracle.com/iavase/8/docs/api/java/util/function/Function.html d) [15 points] List > pathFromRoot(BTNode node) The method returns the path from the root to the given node. If the node is not in the tree, the method throws IllegalArgumentException e) [15 points] int distance(BTNode node 1 , BT Node node2) The method returns the distance from node 1 to node 2 in the tree. If one of the nodes is not in the tree, the method throws IllegalArgumentException f) [30 points ] public Iterator preOrderiterator() The method returns an iterator that performs the preorder traversal on the tree. The iterator must be dynamic in the following sense: if after the iterator is created, and the tree changes in some part that has not been processed by the iterator yet, then the iterator "will see" these changes and output the values in the updated tree when reaching that part of the tree. However, if you change the nodes that have already been processed, then it will have no effect on the iterator. Be careful, do not change the nodes that are currently being processed, as this may have unexpected effects This means you cannot simply create the list with the preorder traversal of the tree in the constructor of the iterator. It will not work in the dynamic sense. You will probably need to implement the iterator in a new class. Please declare the class in the package binarytree. Make sure to submit the java file implementing the iterator. \}