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:

boolean isEmpty() This function should determine whether the binary search tree is empty or not. It returns true if the binary search tree is empty and false otherwise.

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.

void printPostorder() 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 post-order tree traversal strategy.

void insert(T elem) This function should insert the given elem in the binary search tree. elem should be inserted in the correct position in the binary search tree to maintain the sorted order required by a binary search tree.

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.

boolean deleteByCopy(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 copying strategy.

T search(T elem) This function should find the given elem in the binary search tree. If elem is found in the binary search tree it should return the element and otherwise it should return null.

Only implement the methods listed above. You can use both iterative and recursive approaches. You may use your own helper functions to assist in implementing the specification. However, you may not modify any of the given method signatures. Also do not modify any of the other code.

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 ""; }

////// You may not change any code above this line //////

////// Implement the functions below this line //////