Lab 4 (100 pts)
Due Friday, May 22 at 11:59pm on Canvas


Pair Programming Required (or You Will Receive a 0)

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


Lab 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 4
 */

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) {
       
    }
}

  • Starter code for for the insert method is given in Lesson 10
    • You must use this starter code when you write your method
  • Starter code for pre, post and inOrderPrint given in Lesson 11
    • You must use this starter code when you write your method
  • Starter code for search, findMin, and remove given in Lesson 12
    • You must use this starter code when you write your method
  • 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 - rather than copying and pasting code you find online!
  • 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.

Lab 4 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 4
 */
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 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 of the 15 methods is worth 6.7 points (counting wrapper and helper as one method)
  • 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.
    • No credit for any method that does not use the starter code provided in the lesson notes
  • I will grade your Lab using the provided test file, so please make sure your methods work with the given file.