Lab 6 (100 pts)
Due Monday, November 5 at 11:59pm on Canvas


Pair Programming Extra Credit Opportunity (5 pts)

  • Both partners fill in, sign, date, and submit the pair programming contract
  • Only ONE partner submits the lab assignment on Canvas. Please make sure both your names are on ALL the files.


Lab 6 Specifications:
  • Your job for this lab is to write a BST class given the starter code provided below.
  • Create a new project folder in Eclipse and copy and paste the following into a file named BST.java
/**
 * BST.java
 * @author
 * @author
 * CIS 22C Lab 6
 */

import java.util.NoSuchElementException;

public class BST<T extends Comparable<T>> {
    private class Node {
        private T data;
        private Node left;
        private Node right;
       
        public Node(T data) {
            this.data = data;
            left = null;
            right = null;
        }
    }
   
    private Node root;
   
    /***CONSTRUCTORS***/
   
    /**
     * Default constructor for BST
     * sets root to null
     */
    public BST() {
       
    }
   
    /**
     * Copy constructor for BST
     * @param bst the BST to make
     * a copy of
     */
    public BST(final BST<T> bst) {
       
    }
   
    /**
     * Helper method for copy constructor
     * @param node the node containing
     * data to copy
     */
    private void copyHelper(Node node) {
      
    }
   
    /***ACCESSORS***/
   
    /**
     * Returns the data stored in the root
     * @precondition !isEmpty()
     * @return the data stored in the root
     * @throws NoSuchElementException when
     * preconditon is violated
     */
    public T getRoot() throws NoSuchElementException{
        return null;
    }
   
    /**
     * Determines whether the tree is empty
     * @return whether the tree is empty
     */
    public boolean isEmpty() {
        return false;
    }
   
    /**
     * Returns the current size of the
     * tree (number of nodes)
     * @return the size of the tree
     */
    public int getSize() {
        return -1;
    }
   
    /**
     * Helper method for the getSize method
     * @param node the current node to count
     * @return the size of the tree
     */
    private int getSize(Node node) {
        return -1;
    }
   
    /**
     * Returns the height of tree by
     * counting edges.
     * @return the height of the tree
     */
    public int getHeight() {
        return Integer.MIN_VALUE; //remove this. just a default value
    }
   
    /**
     * Helper method for getHeight method
     * @param node the current
     * node whose height to count
     * @return the height of the tree
     */
    private int getHeight(Node node) {
        return Integer.MIN_VALUE; //remove this. just a default value
    }
   
    /**
     * Returns the smallest value in the tree
     * @precondition !isEmpty()
     * @return the smallest value in the tree
     * @throws NoSuchElementException when the
     * precondition is violated
     */
    public T findMin() throws NoSuchElementException{
        return null;
    }
   
    /**
     * Helper method to findMin method
     * @param node the current node to check
     * if it is the smallest
     * @return the smallest value in the tree
     */
    private T findMin(Node node) {
        return null;
    }
   
    /**
     * Returns the largest value in the tree
     * @precondition !isEmpty()
     * @return the largest value in the tree
     * @throws NoSuchElementException when the
     * precondition is violated
     */
    public T findMax() throws NoSuchElementException{
        return null;
    }
   
    /**
     * Helper method to findMax method
     * @param node the current node to check
     * if it is the largest
     * @return the largest value in the tree
     */
    private T findMax(Node node) {
        return null;
    }
   
    /**
     * Searches for a specified value
     * in the tree
     * @param data the value to search for
     * @return whether the value is stored
     * in the tree
     */
    public boolean search(T data) {
        return false;
    }
   
    /**
     * Helper method for the search method
     * @param data the data to search for
     * @param node the current node to check
     * @return whether the data is stored
     * in the tree
     */
    private boolean search(T data, Node node) {
        return false;
    }
   
    /***MUTATORS***/
   
    /**
     * Inserts a new node in the tree
     * @param data the data to insert
     */
    public void insert(T data) {
      
    }
   
    /**
     * Helper method to insert
     * Inserts a new value in the tree
     * @param data the data to insert
     * @param node the current node in the
     * search for the correct location
     * in which to insert
     */
    private void insert(T data, Node node) {
       
    }
   
    /**
     * Removes a value from the BST
     * @param data the value to remove
     * @precondition !isEmpty()
     * @precondition the data is located in the tree
     * @throws NoSuchElementException when the
     * precondition is violated
     */
    public void remove(T data) throws NoSuchElementException{
       
    }
   
    /**
     * Helper method to the remove method
     * @param data the data to remove
     * @param node the current node
     * @return an updated reference variable
     */
    private Node remove(T data, Node node) {      
        return null;
    }
   
       
    /***ADDITONAL OPERATIONS***/
   
    /**
     * Prints the data in pre order
     * to the console
     */
    public void preOrderPrint() {
        System.out.println();
    }
   
    /**
     * Helper method to preOrderPrint method
     * Prints the data in pre order
     * to the console
     */
    private void preOrderPrint(Node node) {
      
    }
   
    /**
     * Prints the data in sorted order
     * to the console
     */
    public void inOrderPrint() {
        System.out.println();
    }
   
    /**
     * Helper method to inOrderPrint method
     * Prints the data in sorted order
     * to the console
     */
    private void inOrderPrint(Node node) {
       
    }
   
    /**
     * Prints the data in post order
     * to the console
     */
    public void postOrderPrint() {
        System.out.println();
    }
   
    /**
     * Helper method to postOrderPrint method
     * Prints the data in post order
     * to the console
     */
    private void postOrderPrint(Node node) {
       
    }
}

  • Hint for writing copy constructor and getSize: Adapt an appropriate tree traversal (preOrderPrint, inOrderPrint, postOrderPrint).
  • Do not search for the code on the internet! If your code does not look like a light adaptation of one of the tree traversal algorithms provided in the class notes, then I will not give you credit for these methods.
    • You can figure it out for yourself!
  • Hint for getHeight: Make sure you recognize that the height of a null if -1 (as covered in class) or you will not get the correct output from this method.
  • Final Hint: Draw the trees that you use in your testing. If you understand what the tree looks like then you will know what output the methods are supposed to give.
Required Unit Tests
  • You are required to write JUnit tests for the following methods (3 assertEquals calls per test file):
  • Note that the required names of the files are provided along with the method below:
    • copy constructor - CopyTest.java
    • getRoot - GetRootTest.java
    • isEmpty - IsEmptyTest.java
    • getSize - GetSizeTest.java
    • getHeight - GetHeightTest.java
    • findMin - FindMinTest.java
    • findMax - FindMaxTest.java
    • search - SearchTest.java
    • insert - InsertTest.java
    • remove - RemoveTest.java

Lab 6 Test File:
  • You will be graded using the below BST test file.
  • Please test your methods using the below test file to make sure your methods are working as the professor expects

import java.util.NoSuchElementException;

/**
 * BSTTest.java
 * @author parrishj
 * CIS 22C, Lab 6
 */
public class BSTTest {
    public static void main(String[] args) {
        BST<Integer> intBst = new BST<Integer>();
        BST<Double> doubleBst = new BST<Double>();
        BST<Character> charBst = new BST<Character>();
       

        System.out.println("**Integer BST Tests**\n");
        System.out.println("Should be empty (true): " + intBst.isEmpty());
        System.out.println("Size of an empty tree (0): " + intBst.getSize());
        System.out.println("Height of an empty tree, i.e. root is null (-1): " + intBst.getHeight());
        intBst.insert(10);
        System.out.println("Inserting 10. 10 should be root: " + intBst.getRoot());
        System.out.println("Inserting 22, 12, 41, 17, 68...");
        intBst.insert(22);
        intBst.insert(12);
        intBst.insert(41);
        intBst.insert(17);
        intBst.insert(68);
        System.out.println("InOrderPrint: Should print out 10 12 17 22 41 68:");
        intBst.inOrderPrint();
        System.out.println("PreOrderPrint: Should print out 10 22 12 17 41 68:");
        intBst.preOrderPrint();
        System.out.println("PostOrderPrint: Should print out 17 12 68 41 22 10:");
        intBst.postOrderPrint();
       
        System.out.println("Should not be empty (false); " + intBst.isEmpty());
        System.out.println("10 should still be root: " + intBst.getRoot());
        System.out.println("Minimum should be 10: " + intBst.findMin());
        System.out.println("Maximum should be 68: " + intBst.findMax());
        System.out.println("Size should be 6: " + intBst.getSize());
        System.out.println("Height should be 3: " + intBst.getHeight());
        System.out.println("Searching for 20 (false): " + intBst.search(20));
        System.out.println("Searching for 17 (true): " + intBst.search(17));
        System.out.println("Removing 17...");
        intBst.remove(17);
        System.out.println("Searching for 17 (false): " + intBst.search(17));
        System.out.println("InOrderPrint: Should print out 10 12 22 41 68:");
        intBst.inOrderPrint();
       
        System.out.println( "Copying the tree...");
        BST<Integer> intBstCopy = new BST<Integer>(intBst); //copying intBst
        System.out.println("InOrderPrint: Copy should print out 10 12 22 41 68:");
        intBstCopy.inOrderPrint();
        System.out.println("Testing for deep copy...Removing 10 from copy...");
        intBstCopy.remove(10);
        System.out.println("InOrderPrint: Copy should print out 12 22 41 68:");
        intBstCopy.inOrderPrint();
        System.out.println("InOrderPrint: Original should print out 10 12 22 41 68:");
        intBst.inOrderPrint();
        System.out.println("Copy size (4): " + intBstCopy.getSize());
        System.out.println("Original size (5): " + intBst.getSize());
       
        System.out.println("\n\n**Character BST Tests**\n");
        System.out.println("Inserting D, A, C, S, B, P...");
        charBst.insert('D');
        charBst.insert('A');
        charBst.insert('C');
        charBst.insert('S');
        charBst.insert('B');
        charBst.insert('P');
        charBst.insert('Z');
       
        System.out.println("InOrderPrint: Should print out A B C D P S Z:");
        charBst.inOrderPrint();
        System.out.println("PreOrderPrint: Should print out D A C B S P Z:");
        charBst.preOrderPrint();
        System.out.println("PostOrderPrint: Should print out B C A P Z S D:");
        charBst.postOrderPrint();
        System.out.println("Should not be empty (false); " + charBst.isEmpty());
        System.out.println("Root should be D: " + charBst.getRoot());
        System.out.println("Minimum should be A: " + charBst.findMin());
        System.out.println("Maximum should be Z: " + charBst.findMax());
        System.out.println("Size should be 7: " + charBst.getSize());
        System.out.println("Height should be 3: " + charBst.getHeight());
        System.out.println("Searching for Z (true): " + charBst.search('Z'));
        System.out.println("Searching for D (true): " + charBst.search('D'));
        System.out.println("Searching for Q (false): " + charBst.search('Q'));
        System.out.println("Checking 3 cases of remove....");
        System.out.print("Removing Z (easy case): ");
        charBst.remove('Z');
        charBst.inOrderPrint();
        System.out.print("Removing C (medium case): ");
        charBst.remove('C');
        charBst.inOrderPrint();
        System.out.print("Removing D (hard case): ");
        charBst.remove('D');
        charBst.inOrderPrint();
       
        System.out.println( "Copying the tree...");
        BST<Character> charBstCopy = new BST<Character>(charBst); //copying intBst
        System.out.println("InOrderPrint: Copy should print out A B P S:");
        charBstCopy.inOrderPrint();
        System.out.println("Testing for deep copy...Inserting Q in the copy...");
        charBstCopy.insert('Q');
        System.out.println("InOrderPrint: Copy should print out A B P Q S:");
        charBstCopy.inOrderPrint();
        System.out.println("InOrderPrint: Original should print out A B P S:");
        charBst.inOrderPrint();
        System.out.println("Copy size (5): " + charBstCopy.getSize());
        System.out.println("Original size (4): " + charBst.getSize());
       
        System.out.println("\n\n**Testing error messages**\n");
       
        try {
            System.out.println("Error for getRoot. Tree is empty.");
            doubleBst.getRoot();
        } catch (NoSuchElementException e) {
            System.out.println(e.getMessage());
        }
       
        try {
            System.out.println("Error for remove. Element not found.");
            charBstCopy.remove('Z');
        } catch (NoSuchElementException e) {
            System.out.println(e.getMessage());
        }
       
        try {
            System.out.println("Error for remove. Tree is empty.");
            doubleBst.remove(3.5);
        } catch (NoSuchElementException e) {
            System.out.println(e.getMessage());
        }
       
        try {
            System.out.println("Error for findMin. Tree is empty.");
            doubleBst.findMin();
        } catch (NoSuchElementException e) {
            System.out.println(e.getMessage());
        }
       
        try {
            System.out.println("Error for findMax. Tree is empty.");
            doubleBst.findMax();
        } catch (NoSuchElementException e) {
            System.out.println(e.getMessage());
        }
       
    }

}
What to Submit
  • Submit your BST.java and your 10 JUnit test classes (listed above in the section "Required Unit Tests") to Canvas.
  • Note that is is recommended that you write your own BSTTEst.java file to test your methods as you go along but it is not a requirement for this Lab.
  • Note that you should not submit BSTTEst.java
  • -5 points for submitting your files as a compressed file type such as zip. Please upload all 11 files directly to Canvas.
  • Optional: Pair programming contract. One partner should submit the contract along with the 11 java files. The other partner should submit the contract only.
How You Will Be Graded
  • Each method is worth 6 points (counted as wrapper and helper as one method) and the JUnit test classes are worth 1.5 points each.
  • No credit if you alter the Node class, add or remove variables from the BST class, or add or alter any BST methods from those provided.
    • You are only allowed to implement the methods whose signatures are provided.
  • I will grade your Lab using the provided test file, so please make sure your methods work with the given file.