1. Complete the height() method in BinaryTree.java, which is used to return the height of this binary tree. Hint: Use recursive algorithm, you can use a helper method.

2. Complete the isCompleteBinaryTree() method in BinaryTree.java, which returns if the binary tree is complete.

Please do not modify TestBinaryTree.java

Changes are required in BinaryTree.java

So Binary Tree.java:

import java.util.LinkedList;
	import java.util.Queue;
	public class BinaryTree {
	public TreeNode root;
	public BinaryTree(){
	}
	public static class TreeNode {
	public E element;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(E o) {
	element = o;
	}
	}
	/******************************************************************
	* Return the height of this binary tree.
	* The height of the tree is the height of root node.
	* Hint: Use recursive algorithm, you can use a helper method
	* ****************************************************************/
	public int height(){
	//TODO
	return 0;
	}
	/******************************************************************
	* Return if the binary tree is complete
	* Hint: scan the node from left to right by level, if there is a
	* node has no left child but has right child, return false; if
	* there is a node has left child, but has no right child, future
	* nodes can not have any child, otherwise return false. You can
	* take printTree method in TestMyTree as a reference.
	* ****************************************************************/
	public boolean isCompleteBinaryTree(){
	//TODO
	return true;
	}
	} Please do not modify the following: public class TestBinaryTree { public static void main(String[] args){ //test case 1 //=================== Test Case 1 =================== //The height of the tree is 3 //The tree is a complete binary tree. System.out.println("=================== Test Case 1 ==================="); BinaryTree bt = new BinaryTree<>(); BinaryTree.TreeNode[] nodes = new BinaryTree.TreeNode[10]; for(int i = 0; i<10; i++){ nodes[i] = new BinaryTree.TreeNode(i); } nodes[0].left = nodes[1]; nodes[0].right = nodes[2]; nodes[1].left = nodes[3]; nodes[1].right = nodes[4]; nodes[2].left = nodes[5]; nodes[2].right = nodes[6]; nodes[3].left = nodes[7]; nodes[3].right = nodes[8]; nodes[4].left = nodes[9]; bt.root = nodes[0]; System.out.println("The height of the tree is "+bt.height()); if(bt.isCompleteBinaryTree()){ System.out.println("The tree is a complete binary tree."); }else{ System.out.println("The tree is NOT a complete binary tree."); } //test case 2 //=================== Test Case 2 =================== //The height of the tree is 3 //The tree is NOT a complete binary tree. System.out.println("=================== Test Case 2 ==================="); nodes[3].right = null; System.out.println("The height of the tree is "+bt.height()); if(bt.isCompleteBinaryTree()){ System.out.println("The tree is a complete binary tree."); }else{ System.out.println("The tree is NOT a complete binary tree."); } //test case 3 //=================== Test Case 3 =================== //The height of the tree is 3 //The tree is NOT a complete binary tree. System.out.println("=================== Test Case 3 ==================="); BinaryTree bt2 = new BinaryTree<>(); BinaryTree.TreeNode[] nodes2 = new BinaryTree.TreeNode[10]; for(int i = 0; i<7; i++){ nodes2[i] = new BinaryTree.TreeNode((char)(i+'a')); } nodes2[0].left = nodes2[1]; nodes2[0].right = nodes2[2]; nodes2[1].left = nodes2[3]; nodes2[1].right = nodes2[4]; nodes2[2].right = nodes2[5]; nodes2[3].left = nodes2[6]; bt2.root = nodes2[0]; System.out.println("The height of the tree is "+bt2.height()); if(bt2.isCompleteBinaryTree()){ System.out.println("The tree is a complete binary tree."); }else{ System.out.println("The tree is NOT a complete binary tree."); } //test case 4 //=================== Test Case 4 =================== //The height of the tree is 3 //The tree is a complete binary tree. System.out.println("=================== Test Case 4 ==================="); nodes2[2].left = new BinaryTree.TreeNode((char)('a'+7)); System.out.println("The height of the tree is "+bt2.height()); if(bt2.isCompleteBinaryTree()){ System.out.println("The tree is a complete binary tree."); }else{ System.out.println("The tree is NOT a complete binary tree."); } //test case 5 //=================== Test Case 5 =================== //The height of the tree is 2 //The tree is a complete binary tree. System.out.println("=================== Test Case 5 ==================="); nodes2[3].left = null; System.out.println("The height of the tree is "+bt2.height()); if(bt2.isCompleteBinaryTree()){ System.out.println("The tree is a complete binary tree."); }else{ System.out.println("The tree is NOT a complete binary tree."); } //test case 6 //=================== Test Case 6 =================== //The height of the tree is 2 //The tree is NOT a complete binary tree. System.out.println("=================== Test Case 6 ==================="); nodes2[1].left = null; System.out.println("The height of the tree is "+bt2.height()); if(bt2.isCompleteBinaryTree()){ System.out.println("The tree is a complete binary tree."); }else{ System.out.println("The tree is NOT a complete binary tree."); } } }