Using JAVA. You have been given a partially implemented binary search tree class and a binary search tree node class to use. Your task is to implement the following methods in the binary search tree class BinTree according to the given specification:

BinTreeNode clone() This function should create a new binary tree (with its own nodes) that is a clone of the original binary search tree. This function should return the root node of the new binary tree.

Note: Make sure you dont make any changes to the original tree.

BinTreeNode mirror() This function should create a new binary tree (with its own nodes) that is the mirror image across the vertical axis of the original binary search tree. This function should return the root node of the new binary tree. Note: Make sure you dont make any changes to the original tree. void printPreorder() This function should print out all the elements in the binary search tree as a space separated list that is terminated by a newline. This function should use the pre-order tree traversal strategy.

boolean deleteByMerge(T elem) This function should delete the given elem from the binary search tree. It returns true if elem is removed successfully and false otherwise. This function should use the delete by merging strategy.

Given Code:

////////BinTreeNode.java//////////

public class BinTreeNode> { protected T element; protected BinTreeNode left, right; public BinTreeNode() { left = right = null; } public BinTreeNode(T el) { this(el,null,null); } public BinTreeNode(T el, BinTreeNode lt, BinTreeNode rt) { this.element = el; left = lt; right = rt; } public String toString() { String out = element.toString(); out += " [L: "+ (left == null ? null : left.element) + "] "; out += " [R: "+ (right == null ? null : right.element) + "] "; return out; } }

////////BinTree.java//////////

@SuppressWarnings("unchecked") public class BinTree> { protected BinTreeNode root = null; protected static int count = 0; public BinTree() {} public void clear(){ root = null; } public String inorder(BinTreeNode node) { boolean verbose = true; if (node != null) { String result = ""; result += inorder(node.left); if (verbose) { result += node.toString()+" "; } else { result += node.element.toString() + " "; } result += inorder(node.right); return result; } return ""; }

public boolean isEmpty() { return (root == null); }

public void insert(T element) { BinTreeNode nodePtr = root,prevNode = null; while(nodePtr != null){ prevNode = nodePtr; if(nodePtr.element.compareTo(element) > 0) nodePtr = nodePtr.left; else nodePtr = nodePtr.right; } if(isEmpty()) root = new BinTreeNode(element); else if(prevNode.element.compareTo(element) > 0) prevNode.left = new BinTreeNode(element); else prevNode.right = new BinTreeNode(element); }

public T search(T element) { //Your code goes here BinTreeNode nodePtr = root; while(nodePtr != null){ if(nodePtr.element == element) return nodePtr.element; else if(nodePtr.element.compareTo(element) > 0) nodePtr = nodePtr.left; else nodePtr = nodePtr.right; } return null; } ////// You may not change any code above this line ////// ////// Implement the functions below this line //////