CSCI 162 — Lab 9

Due: Sunday December 9, 2018 @ 11:59PM

Binary Search Tree

Handout Code is available HERE

Goals

• to use a binary tree node class - BTNode<E>
• to build a binary search tree class
• to gain more recursion experience

Overview

You MUST use binary trees as developed in class for this assignment. The approach differs from the one in the text, but refer to the text for examples and a related explanation. If there is a conflict, what we've done in class is right. As always, ask for help if you are confused.

For this assignment, you will write the insert and remove method for a program that builds a binary search tree of characters.

• It will read in two lines of characters.
• It will put the first line in a binary search tree and then print the tree's contents both sideways graphically and in inorder fashion.
• It will then read in the second line of input removing the characters of the second line from the binary search tree (if they are there).
• Finally, it will print the modified tree's contents both sideways and in inorder fashion.

In both cases, there may be duplicate characters in the lines. This is okay. Store all copies of a character in separate nodes. If there are three copies of a character in the first line, and two are removed because they are in the second line, one copy remains in the tree.

Specifications

You are tasked with implementing four methods in BinarySearchTree.java

/**
  * insert item into tree rooted at node
  * look ahead to insert before falling off end of subtree
  *
  * @param node
  *            root of current subtree
  * @param item
  *            item to be inserted in tree
  */
private void insert(BTNode<E> root, E item);

/**
  * remove target from tree rooted at root with provided parent
  *
  * @param node
  *            node at top of current sub-tree that may contain target
  * @param data
  *            item to be removed if it exists in tree
  */
private BTNode<E> remove (BTNode<E> node, E data)

/**
  * Find the rightmost node (largest value), disconnect it from the tree, and
  * return its data.
  * 
  * Preconditions: node and parent are not null.
  *
  * @param parent
  *            parent of this node so that it can be deleted
  * @param node
  *            current node that potentially is rightmost
  * @return the data from the rightmost node which has been removed
  */
private E removeLargest (BTNode<E> parent, BTNode<E> node)

/**
 * Replaces old child with new child in parent's links. Figures out whether it
 * was a left or right child.
 *
 * Precondition: parent is not null.
 *
 * @param parent
 *            node that has children with one needing replacement
 * @param oldChild
 *            node that will be discarded
 * @param newChild
 *            node that will be attached in oldChild's place
 */
private void replaceChild (BTNode<E> parent, BTNode<E> oldChild, BTNode<E> newChild)

insert and remove MUST be implemented recursively

Binary Search Tree Semantics

In a binary search tree, the entries of the nodes can be compared with a total order semantics. These two rules are followed for every node n:

1. Every element in n's left subtree is less than or equal to the element in node n.
2. Every element in n's right subtree is greater than the element in node n.

Sample Input and Output

Enter a line of input to insert: marauder
After inserting: aademrru

                -
            u
                -
        r
                -
            r
                -
    m
                    -
                e
                    -
            d
                -
        a
                -
            a
                -

Line of characters to remove: rummage
After removing: adr

            -
        r
            -
    d
            -
        a
            -

Hints

1. Implement insert first. Think about the condition necessary for inserting into a BST
2. Start iteratively implementing remove. Think about all the various cases for removal
   • If the node with target value doesn't exist
   • If the node with target value does exist
     • If it has no children
     • If it has a left child
     • If it has a right child
     • If it has two children
3. Determine how replaceChild and removeLargest fit into the logic of remove
4. Implement replaceChild (hint: it's not recursive)
5. Implement removeLargest (hint: this can be recursive or it can use a while-loop)
6. Test ALL THE THINGS

Submission

Submit this program as Lab 9: Binary Search Tree

Grading

• 90 Points for the JUnit Tests
• 10 Points for comments, name, and clean formatting

NOTE: credit will ONLY be given if insert AND remove are implemented recursively