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


Pair Programming Required or No Credit!

  • Both partners fill in, sign and date the pair programming contract and BOTH partners submit.
  • 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(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;
    }

   
    /**
     * Determines whether two trees store
     * identical data in the same structural
     * position in the tree
     * @param o another Object
     * @return whether the two trees are equal
     */
    @Override public boolean equals(Object o) {
        return false;
    }
   
    /**
     * Helper method for the equals method
     * @param node1 the node of the first bst
     * @param node2 the node of the second bst
     * @return whether the two trees contain
     * identical data stored in the same structural
     * position inside the trees
     */   
    private boolean equals(Node node1, Node node2) {
        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;
    }
   
       
    /***ADDITIONAL 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, getSize: Adapt an appropriate tree traversal (preOrderPrint, inOrderPrint, postOrderPrint).
    • 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 equals: This method requires a more significant adaptation of one of the tree traversals.
  • 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.
  • For all of these recursive methods, you will understand the methods better if you draw the method call stack and trace through an example of pushing and popping method calls (stack frames) from the stack memory.
  • 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
    • equals - EqualsTest.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("Two copies are equal (true): " + intBstCopy.equals(intBst));
        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("Two copies are equal (false): " + intBstCopy.equals(intBst));
       
        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 11 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.
  • Both partners submit pair programming contract. Only one partner needs to submit the source code files.
  • Please submit each file separately (no zip files or other compressed file type -5 pts).
  • Please remove all package statements before submitting (-5 pts).

How You Will Be Graded
  • Each method is worth 5 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.