1. Binary Search Tree a. Add the following implementations to BinarySearchTree.java i. insert (AnyType x): insert key x into the Binary Search Tree. ii. isFull (): returns true if the tree is full, else false. iii. countLeafNodes (): returns the number of leaf nodes in the tree.

package assignment2;

/** * Implements a Binary Search Tree. * * @author CSC330 * @param */ public class BinarySearchTree> {

protected BinaryNode root;

public BinarySearchTree() { root = null; }

/** * Insert into the tree; duplicates are ignored. * * @param x the item to insert. * @param root * @return */ protected BinaryNode insert(AnyType x, BinaryNode root) { /** * WRITE YOUR CODE HERE */

return root; }

/** * Counts the number of leaf nodes in this tree. * * @param t The root of the tree. * @return */ private int countLeafNodes(BinaryNode root) { /* WRITE YOUR CODE HERE */ return 0; }

/** * Checks if the tree is a full tree. * * @param t The root of the tree. * @return */ private boolean isFull(BinaryNode root) { /* WRITE YOUR CODE HERE */ return false; }

public void insert(AnyType x) { root = insert(x, root); }

/** * Counts the number of leaf nodes in a tree. * * @return */ public int countLeafNodes() { return countLeafNodes(root); }

/** * Checks if the tree is full. * * @return */ public boolean isFull() { return isFull(root); }

/** * Remove from the tree. Nothing is done if x is not found. * * @param x the item to remove. */ public void remove(AnyType x) { root = remove(x, root); }

/** * Internal method to remove from a subtree. * * @param x the item to remove. * @param root the node that roots the subtree. * @return the new root of the subtree. */ protected BinaryNode remove(AnyType x, BinaryNode root) { // If item not found, do nothing. if (root == null) { return root; }

int compareResult = x.compareTo(root.element);

if (compareResult < 0) { root.left = remove(x, root.left); } else if (compareResult > 0) { root.right = remove(x, root.right); } // Two children. else if (root.left != null && root.right != null) { root.element = findMin(root.right).element; root.right = remove(root.element, root.right); } // Zero or one child. else { root = (root.left != null) ? root.left : root.right; }

return root; }

/** * Find an item in the tree. * * @param x the item to search for. * @return true if not found. */ public boolean contains(AnyType x) { return contains(x, root); }

private boolean contains(AnyType x, BinaryNode root) { if (root == null) { return false; }

int compareResult = x.compareTo(root.element);

if (compareResult < 0) { return contains(x, root.left); } else if (compareResult > 0) { return contains(x, root.right); } else { return true; // Match with current node } }

/** * Find the smallest item in the tree. * * @return smallest item or null if empty. * @throws Exception */ public AnyType findMin() throws Exception { if (isEmpty()) { throw new Exception(); } return findMin(root).element; }

private BinaryNode findMin(BinaryNode root) { if (root == null) { return null; } else if (root.left == null) { return root; // found the leftmost node } else { return findMin(root.left); } }

/** * Test if the tree is logically empty. * * @return true if empty, false otherwise. */ public boolean isEmpty() { return root == null; }

/** * Calculate the height of the tree. * * @return the height. */ public int height() {

return height(this.root);

}

/** * Internal method to compute height of a subtree. * * @param root the node that roots the subtree. * @return */ protected int height(BinaryNode root) { return root == null ? -1 : 1 + Math.max(height(root.left), height(root.right)); }

public BinaryNode getRoot() { return root; }

public void setRoot(BinaryNode root) { this.root = root; }

public void printSideways(String label) {

System.out.println( " -------------------------------" + label + "----------------------------"); printSideways(root, ""); }

private void printSideways(BinaryNode root, String indent) { if (root != null) { printSideways(root.right, indent + " "); System.out.println(indent + root.element); printSideways(root.left, indent + " "); }

} }