Please use following code to do the following and remove any uneeded code and comments and demonstrate program with public void main string args.

(Add new methods in BST) Add the following new methods in BST

//Displays the nodes in a breadthFirstTraversal

public void breadthFirstTraversal()

//Returns the height of this binary tree

public int height()

(Find the leaves) Add a method in the BST class to return the number of the

leaves as follows:

/** Returns the number of leaf nodes */

publicintgetNumberOfLeaves()

(Find the nonleaves) Add a method in the BST class to return the number of the nonleaves as follows:

/** Returns the number of nonleaf nodes */

publicintgetNumberofNonLeaves()

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

public class BinaryTree> implements Cloneable { protected TreeNode root; protected int size = 0;

/** Create a default binary tree */ public BinaryTree() { }

/** Create a binary tree from an array of objects */ public BinaryTree(E[] objects) { for (int i = 0; i < objects.length; i++) insert(objects[i]); }

/** Returns true if the element is in the tree */ public boolean search(E e) { TreeNode current = root; // Start from the root

while (current != null) { if (e.compareTo(current.element) < 0) { current = current.left; } else if (e.compareTo(current.element) > 0) { current = current.right; } else // element matches current.element return true; // Element is found }

return false; }

/** Insert element o into the binary tree * Return true if the element is inserted successfully */ public boolean insert(E e) { if (root == null) root = createNewNode(e); // Create a new root else { // Locate the parent node TreeNode parent = null; TreeNode current = root; while (current != null) if (e.compareTo(current.element) < 0) { parent = current; current = current.left; } else if (e.compareTo(current.element) > 0) { parent = current; current = current.right; } else return false; // Duplicate node not inserted

// Create the new node and attach it to the parent node if (e.compareTo(parent.element) < 0) parent.left = createNewNode(e); else parent.right = createNewNode(e); }

size++; return true; // Element inserted }

protected TreeNode createNewNode(E e) { return new TreeNode(e); }

/** Inorder traversal from the root*/ public void inorder() { inorder(root); }

/** Inorder traversal from a subtree */ protected void inorder(TreeNode root) { if (root == null) return; inorder(root.left); System.out.print(root.element + " "); inorder(root.right); }

/** Postorder traversal from the root */ public void postorder() { postorder(root); }

/** Postorder traversal from a subtree */ protected void postorder(TreeNode root) { if (root == null) return; postorder(root.left); postorder(root.right); System.out.print(root.element + " "); }

/** Preorder traversal from the root */ public void preorder() { preorder(root); }

/** Preorder traversal from a subtree */ protected void preorder(TreeNode root) { if (root == null) return; System.out.print(root.element + " "); preorder(root.left); preorder(root.right); }

/** Inner class tree node */ public static class TreeNode> { public E element; public TreeNode left; public TreeNode right;

public TreeNode(E e) { element = e; } }

/** Get the number of nodes in the tree */ public int getSize() { return size; }

/** Returns the root of the tree */ public TreeNode getRoot() { return root; }

/** Returns a path from the root leading to the specified element */ public java.util.ArrayList> path(E e) { java.util.ArrayList> list = new java.util.ArrayList>(); TreeNode current = root; // Start from the root

while (current != null) { list.add(current); // Add the node to the list if (e.compareTo(current.element) < 0) { current = current.left; } else if (e.compareTo(current.element) > 0) { current = current.right; } else break; }

return list; // Return an array of nodes }

/** Delete an element from the binary tree. * Return true if the element is deleted successfully * Return false if the element is not in the tree */ public boolean delete(E e) { // Locate the node to be deleted and also locate its parent node TreeNode parent = null; TreeNode current = root; while (current != null) { if (e.compareTo(current.element) < 0) { parent = current; current = current.left; } else if (e.compareTo(current.element) > 0) { parent = current; current = current.right; } else break; // Element is in the tree pointed by current }

if (current == null) return false; // Element is not in the tree

// Case 1: current has no left children if (current.left == null) { // Connect the parent with the right child of the current node if (parent == null) { root = current.right; } else { if (e.compareTo(parent.element) < 0) parent.left = current.right; else parent.right = current.right; } } else { // Case 2: The current node has a left child // Locate the rightmost node in the left subtree of // the current node and also its parent TreeNode parentOfRightMost = current; TreeNode rightMost = current.left;

while (rightMost.right != null) { parentOfRightMost = rightMost; rightMost = rightMost.right; // Keep going to the right }

// Replace the element in current by the element in rightMost current.element = rightMost.element;

// Eliminate rightmost node if (parentOfRightMost.right == rightMost) parentOfRightMost.right = rightMost.left; else // Special case: parentOfRightMost == current parentOfRightMost.left = rightMost.left; }

size--; return true; // Element inserted }

/** Obtain an iterator. Use inorder. */ public java.util.Iterator iterator() { return inorderIterator(); }

/** Obtain an inorder iterator */ public java.util.Iterator inorderIterator() { return new InorderIterator(); }

/** Obtain a postorder iterator */ public java.util.Iterator postorderIterator() { return new PostorderIterator(); }

/** Obtain a preorder iterator */ public java.util.Iterator preorderIterator() { return new PreorderIterator(); }

//Inner class PreorderIterator class PreorderIterator implements java.util.Iterator { // Store the elements in a list private java.util.ArrayList list = new java.util.ArrayList(); private int current = 0; // Point to the current element in list

public PreorderIterator() { preorder(); // Traverse binary tree and store elements in list }

/** Preorder traversal from the root **/ private void preorder() { preorder(root); }

/** Preorder traversal from a subtree **/ private void preorder(TreeNode root) { if (root == null) return; list.add(root.element); preorder(root.left); preorder(root.right); }

/** Next element for traversing? */ public boolean hasNext() { if (current < list.size()) return true;

return false; }

/** Get the current element and move cursor to the next */ public Object next() { return list.get(current++); }

/** Remove the current element and refresh the list */ public void remove() { delete(list.get(current)); // Delete the current element list.clear(); // Clear the list inorder(); // Rebuild the list } }

// Inner class PostorderIterator class PostorderIterator implements java.util.Iterator { // Store the elements in a list private java.util.ArrayList list = new java.util.ArrayList(); private int current = 0; // Point to the current element in list

public PostorderIterator() { postorder(); // Traverse binary tree and store elements in list }

/** Postorder traversal from the root **/ private void postorder() { postorder(root); }

/** Postorder traversal from a subtree **/ private void postorder(TreeNode root) { if (root == null) return; postorder(root.left); postorder(root.right); list.add(root.element); }

/** Next element for traversing? */ public boolean hasNext() { if (current < list.size()) return true;

return false; }

/** Get the current element and move cursor to the next */ public Object next() { return list.get(current++); }

/** Remove the current element and refresh the list */ public void remove() { delete(list.get(current)); // Delete the current element list.clear(); // Clear the list inorder(); // Rebuild the list } }

// Inner class InorderIterator class InorderIterator implements java.util.Iterator { // Store the elements in a list private java.util.ArrayList list = new java.util.ArrayList(); private int current = 0; // Point to the current element in list

public InorderIterator() { inorder(); // Traverse binary tree and store elements in list }

/** Inorder traversal from the root*/ private void inorder() { inorder(root); }

/** Inorder traversal from a subtree */ private void inorder(TreeNode root) { if (root == null)return; inorder(root.left); list.add(root.element); inorder(root.right); }

/** Next element for traversing? */ public boolean hasNext() { if (current < list.size()) return true;

return false; }

/** Get the current element and move cursor to the next */ public Object next() { return list.get(current++); }

/** Remove the current element and refresh the list */ public void remove() { delete(list.get(current)); // Delete the current element list.clear(); // Clear the list inorder(); // Rebuild the list } }

/** Remove all elements from the tree */ public void clear() { root = null; size = 0; }

public Object clone() { BinaryTree tree1 = new BinaryTree();

copy(root, tree1);

return tree1; }

private void copy(TreeNode root, BinaryTree tree) { if (root != null) { tree.insert(root.element); copy(root.left, tree); copy(root.right, tree); } }

/** Return the leaf node count **/ public int getNumberOfLeaves() { return getNumberOfLeaves(root); }

/** Return the leaf node count **/ public int getNumberOfNonLeaves() { return getNumberOfNonLeaves(root); }

/** Count the non-leaf nodes **/ private int getNumberOfNonLeaves(TreeNode root) { if (root == null) return 0; int count = getNumberOfNonLeaves(root.left) + getNumberOfNonLeaves(root.right); if (root.left != null || root.right != null) count++; return count; }

/** Count the leaf nodes **/ private int getNumberOfLeaves(TreeNode root) { if (root == null) return 0; if (root.left == null && root.right == null) return 1; return getNumberOfLeaves(root.left) + getNumberOfLeaves(root.right); }

public E findMin() { if (root == null) return null; return findMin(root); }

public E findMin(TreeNode root) { if (root == null) return null; if (root.left != null) return findMin(root.left); return root.element; }

public E findMax() { if (root == null) return null; return findMax(root); }

public E findMax(TreeNode root) { if (root == null) return null; if (root.right != null) return findMax(root.right); return root.element; } }