Complete the BinaryTreeNode and BinaryTree classes given. You will be required to write several methods for each class and any additional methods that you feel might be useful (extra methods in the BinaryTreeNode, toString methods, etc.).

Required Methods:

Write an equals method for both the BinaryTreeNode and BinaryTree classes.

Write a method called deepCopy() for the BinaryTree class that returns a deep copy of the calling object. A deepCopy() method for BinaryTreeNode has been provided. Seehttp://www.codeproject.com/Articles/28952/Shallow-Copy-vs-Deep-Copy-in-NET for an explanation of deep copy.

Write a method in BinaryTree class called combine(BinaryTreeNode root, BinaryTree t, boolean left) that takes in a root, a binary tree and a boolean that determines if the calling tree is the left child (true) or the right child (false). Calling tree means the this tree when writing the method. The method should return a new BinaryTree object that has the given root, whose left child is the root of the appropriate BinaryTree and whos right child is the root of the appropriate BinaryTree. Note left and right are determined by the boolean (if true the calling tree is the left child and the passing tree is the right child, if false the parameter tree is the left value and calling tree is right child). The new tree should not reference any of the parameters (deep copy). See the pictures attached to help illustrate the problem.

Write a method called size() in the BinaryTree class that returns (an int) the number of nodes in the tree. Note that the size() method in BinaryTreeNode class has been provided.

Write a method called height() in the BinaryTree and BinaryTreeNode class. The method will return an int that represents the height of the total tree. The root of the tree is at height 1, the children of the root are at height 2, ect. The total height of the tree is the maximum height of all nodes in the tree. Note: this is slightly different than other sources definition, some will take the root to be at height 0.

Write a method in both classes called mirror( ) that takes the binary tree and changes the tree to its mirror. For reference a picture of two trees that are mirrors of one another is given. Note that this is changing the calling tree not returning a new one.

Write a method in both classes called full() that returns true if the binary tree is full and complete and false otherwise. A full and complete tree is one in which all nodes other than leafs have two children and all leafs have the same height. This is also known as a perfect binary tree. A picture of a full and complete (perfect) binary tree of height 4 is attached.

Write a method in both classes called inOrder() that returns a string that represents the data held at each node starting with all the nodes of the left child followed by the root then finally all the nodes of the right child. A picture is attached that shows the order in which nodes would be traversed in this method. The string for the tree in the picture should look like this (1)(2)(3)(4)(5)(6)(7)(8)(9)(10). That is every data entry enclosed in a parentheses printed in the in order described above.

Testing

You will need to write at least 2 JUnit methods for each method above except for getters and setters (no tests required for getters and setters although you can write some if you would like!). You will need to submit these to Web-Cat along with the rest of your code. Use standard naming conventions for these JUnit tests (i.e. the JUnit test names must have the word "test" in it somewhere), however we do not mind what you call them. Remember, it would be best if you do not have more than one assert statement per JUnit test case (method). There is no upper limit on how many JUnit test cases you write. Place all your JUnit test cases in one single file ("JUnit Test Case") - you do not need separate files to test,

public class BinaryTree { private BinaryTreeNode root; public BinaryTree() { this(null); } public BinaryTree(BinaryTreeNode newRoot) { this.root = newRoot; } public BinaryTreeNode getRoot() { return root; } public void setRoot(BinaryTreeNode root) { this.root = root; } @Override public boolean equals(Object o) { //To do } public BinaryTree deepCopy() { //To do } public BinaryTree combine(BinaryTreeNode newRoot, BinaryTree t, boolean left) { //To do } public int size(){ //To do } public int height(){ //To do } public boolean full(){ //To do } public void mirror(){ //To do } public String inOrder(){ //To do } } 

public class BinaryTreeNode { private BinaryTreeNode left; private BinaryTreeNode right; private T data; public BinaryTreeNode(){ this(null,null,null); } public BinaryTreeNode(T theData){ this(theData,null,null); } public BinaryTreeNode(T theData, BinaryTreeNode leftChild, BinaryTreeNode rightChild){ data = theData; left = leftChild; right = rightChild; } public int size(){ int size = 0; //the size of the tree //The size of the tree rooted at this node is one more than the //sum of the sizes of its children. if(left != null){ size = size + left.size(); } if(right != null){ size = size + right.size(); } return size + 1; //add one to account for the current node } public BinaryTreeNode getLeft() { return left; } public void setLeft(BinaryTreeNode left) { this.left = left; } public BinaryTreeNode getRight() { return right; } public void setRight(BinaryTreeNode right) { this.right = right; } public T getData() { return data; } public void setData(T data) { this.data = data; } public BinaryTreeNode deepCopy(){ BinaryTreeNode copy = new BinaryTreeNode(this.data); BinaryTreeNode newLeft = null; BinaryTreeNode newRight = null; if (this.left != null) { newLeft = this.left.deepCopy(); copy.setLeft(newLeft); } if (this.right != null) { newRight = this.right.deepCopy(); copy.setRight(newRight); } return copy; } @Override public boolean equals(Object o){ //To do } public int height(){ //To do } public boolean full(){ //To do } public void mirror(){ //To do } public String inOrder(){ //To do } }