Write the following methods into the .java files given below the sample output(Please follow exactly the requirements mentioned below and provide snapshots of your code and output):

a)Write a method public int count() to count the number of nodes in a binary tree.

b)Write a method public boolean isLeaf(BTNode node) to determine if a given binary tree node is a leaf.

c)Write a method public int countLeaves() to count the number of leaves in a binary tree.

d)Write a method int getLevel(T data) to find the level of a node with key data of a binary tree. Assume that the binary tree has distinct keys.

Test program.

Write a test java program that creates the binary tree shown below, traverses it using the breadth-first and depth-first traversals (preorder, inorder, and postorder) and prints the traversal results. It also tests the delete method and the above methods. For example, for the following tree:

////BinaryTree.java////

import java.util.Queue; import java.util.LinkedList; import java.util.NoSuchElementException;

public class BinaryTree> { BTNode root; public BinaryTree() { root = null; } public void purge(){ root = null; } public boolean isEmpty(){ return root == null; } public void insert(T key){ if (root == null) { root = new BTNode(key); return; } BTNode temp; Queue q = new LinkedList(); q.add(root); // Do level order traversal until we find the first empty left or right child. while (!q.isEmpty()) { temp = q.poll(); if (temp.left == null) { temp.left = new BTNode(key); break; } else q.add(temp.left); if (temp.right == null) { temp.right = new BTNode(key); break; } else q.add(temp.right); } } public void deleteByCopying(T data){ if(root == null) throw new UnsupportedOperationException("Tree is empty!"); else if(root.left == null && root.right == null){ if(root.data.equals(data)) root = null; else throw new NoSuchElementException(data + " not in the tree."); return; } Queue queue = new LinkedList(); queue.add(root); BTNode keyNode = null; BTNode currentNode = null; BTNode parentNode = root; boolean found = false; while(! queue.isEmpty()){ currentNode = queue.poll(); if(currentNode.data.equals(data)){ if(! found){ keyNode = currentNode; found = true; } } if(currentNode.left != null){ queue.add(currentNode.left); parentNode = currentNode; } if(currentNode.right != null){ queue.add(currentNode.right); parentNode = currentNode; } } if(! found) throw new NoSuchElementException(data + " not in tree."); while(! queue.isEmpty()){ currentNode = queue.poll(); System.out.print(currentNode.data + " "); if(currentNode.left != null){ queue.add(currentNode.left); parentNode = currentNode; } if(currentNode.right != null){ queue.add(currentNode.right); parentNode = currentNode; } } keyNode.data = currentNode.data; if(parentNode.left == currentNode) parentNode.left = null; else if(parentNode.right == currentNode) parentNode.right = null; } public void levelOrderTraversal(){ // BreadthFirstTraversal levelOrderTraversal(root); }

private void levelOrderTraversal(BTNode root){ if(root == null) return; Queue queue = new LinkedList(); BTNode node = root; queue.add(node); while(! queue.isEmpty()){ node = queue.poll(); System.out.print(node.data + " "); if(node.left != null) queue.add(node.left); if(node.right != null) queue.add(node.right); } } public void inorderTraversal(){ inorderTraversal(root); }

protected void inorderTraversal(BTNode node) { if (node == null) return; inorderTraversal(node.left); System.out.print(node.data + " "); inorderTraversal(node.right); } public void postorderTraversal(){ postorderTraversal(root); } private void postorderTraversal(BTNode node){ if (node == null) return; postorderTraversal(node.left); postorderTraversal(node.right); System.out.print(node.data + " "); } public void preorderTraversal(){ preorderTraversal(root); } private void preorderTraversal(BTNode node){ if (node == null) return; System.out.print(node.data + " ");

preorderTraversal(node.left); preorderTraversal(node.right); } public boolean search(T key){ if(root == null) return false; Queue queue = new LinkedList(); BTNode node = root; queue.add(node); while(! queue.isEmpty()){ node = queue.poll(); if(key.equals(node.data)) return true; if(node.left != null) queue.add(node.left); if(node.right != null) queue.add(node.right); } return false; }

public void printTree(){ printTree(root, "", true); }

// Print the tree private void printTree(BTNode currPtr, String indent, boolean last) { if (currPtr != null) { System.out.print(indent); if (last) { System.out.print("R----"); indent += " "; } else { System.out.print("L----"); indent += "| "; } System.out.println(currPtr.data); printTree(currPtr.left, indent, false); printTree(currPtr.right, indent, true); } }

}

////BTNode.java////

public class BTNode> { protected T data; protected BTNode left, right; public BTNode() { left = right = null; }

public BTNode(T data) { this(data,null,null); }

public BTNode(T data, BTNode left, BTNode right) { this.data = data; this.left = left; this.right = right; } }

////BinaryTreeDriver.java////

public class BinaryTreeDriver{ public static void main(String args[]) { // To be completed } }

2 3 4 5 12 a sample program run is: The number of nodes in the tree is 6 The number of leaf nodes in the tree is 3 The level of node with key 4 is 2 Trying to find the level of node with key 60 ... java.util.NoSuchElementException: Key not in tree. Preorder Traversal is: 124 5 123 Inorder Traversal is: 4 2 12 5 13 Before deleting key 3, level order traversal of binary tree is: 1 2 3 4 5 12 The tree is: R----1 L----2 | L----4 R----5 L----12 R----3 After deleting key 3, level order traversal of binary tree is: 1 2 12 4 5 The tree is: R----1 L----2 L----4 | R----5 R----12