Computer Science 210

Data Structures

Fall 2017, Siena College

In this lab, you will learn more about implementing methods of trees,
in particular, binary search trees that store `double` values.
Rather than working with implementations in the structure package, we
will use a simpler implementation.

You may choose one or two partners in your own lab section to work with on this lab. Only one submission per group is needed.

Getting Set Up

You will receive an email with the
link to follow to set up your GitHub repository
`trees-lab-yourgitname` for this Lab. One member of the
group should follow the link to set up the repository on GitHub,
then that person should email the instructor with the other group
members' GitHub usernames so they can be granted access. This will
allow all members of the group to clone the repository and commit
and push changes to the origin on GitHub.

Please answer lab questions in the `README.md` file in your group's
GitHub repository.

The BST Implementation and Test Code

To start, study the implementation of the `BinarySearchTree` class
and take a look at the `main` method in `Test.java`.

Warmup Recursive Tree Methods

Add **recursive** implementations of methods in
`BinarySearchTree` to compute and return the sum of all values in
the BST (5 points):

public double sum();

and to compute the number of leaf nodes in the BST (5 points):

public int numLeaves();

In each case, you will need to write a recursive helper method. Also
add code to test each in the `main` method of `Test.java` (2
points). You will need to add a couple more BSTs to test all
important cases.

More Recursive Tree Methods

Add **recursive** implementations of methods in
`BinarySearchTree` to do each of the following.

A `contains` method, which returns `true` if value `v` is in
the tree and `false` otherwise. (6 points)

public boolean contains(double v);

A method `numAs`, which returns a count of the number of values in
the tree whose value is in the "A" grade range, i.e., 90-100. (6 points)

public int numAs();

A method `getSmallest`, which returns the smallest data value in
the tree. To keep things simple, assume there is always at least one
value in the tree, so that a smallest value exists. (5 points)

public double getSmallest();

As with the warmup recursive methods, each of these will require a
recursive helper method. Also add code to test each in the `main`
method of `Test.java` (3 points).

Note: to earn full credit, your implementations should only search the parts of the tree where the values being sought might be found. Take advantage of the fact that you are dealing with a BST!

Some Iterative Tree Methods

Now, let's write some BST methods without recursion. Documentation is
provided for what each of these should do in
`BinarySearchTree.java` and points will be awarded for passing
tests in the `main` method of `TestBinarySearchTree.java`. A
total of 22 points are available for passing the tests for these three
methods.

public void addIterative(double value); public double getLargestIterative(); public void removeLargestIterative();

Removing Arbitrary Values from a BST

We conclude by implementing a more complicated BST method: removing a single instance (note that there could be more than one in the tree) of an arbitrary value from the BST.

public void remove(double value);

You will implement this method iteratively, and we will do it in a two steps: 1) finding the node that contains the value, and then 2) writing the code to remove it. There are several cases to consider, so the lab will step you through each part of the implementation. A total of 37 points plus 5 bonus points are available for passing the tests of this method.

To remove a value, you first must be able to find the `Node`
containing the value to be removed. Do this now in the `remove`
method by using the provided variables `current` and
`parentOfCurrent`, each of which is of type `Node`. Start by
initializing `current` to the root and `parentOfCurrent` to
`null`. Then use a loop to move `current` down the tree until it
either reaches a `Node` containing the value or becomes `null`
(meaning the value is not in the tree). The variable
`parentOfCurrent` needs to follow current down the tree, always one
node behind it (since our BST structure does not maintain parent
references in its nodes). The variable `parentOfCurrent` will be
necessary when removing the value in step 2.

Now, we remove the `Node` containing the value. To remove the
`Node`, there are 4 cases to deal with. Implement and test each
case (using the `main` method in `TestBinarySearchTree`).

- Case 1
- The
`current`node is null, indicating the value was not found in the tree. In this case, the method just returns with no further work. This case is already implemented for you! (But you also get no further credit for completing it...) - Case 2
- The
`current`node has no children. In this case, change the link of`parentOfCurrent`that refers to`current`to`null`. This is illustrated below when removing the value 9 from the tree. Run the test program and make sure you get full points for this case before going on to the next case. - Case 3
- The
`current`node has only one child. For example, we might be removing 9 from the tree on the left below.In this situation, change the

`parentOfCurrent`'s child link and make it point to the only child of 9, as shown on the right above. Observe that node 9 is no longer part of the tree (because you can't get to it from the root). Java's garbage collection will eventually reclaim its memory.Note that in this example,

`current`was to the left of`parentOfCurrent`so we changed`parentOfCurrent`'s left child link. But if`current`had been on the right of`parentOfCurrent`, we would have changed`parentOfCurrent`'s right child link instead. So you'll have to test for this and change the correct link. - Case 4
- In the last case,
`current`has two children. You can take care of this case in two substeps. First, find the largest element in`current`'s left subtree and copy its data into the`current`node, overwriting the target value and thus removing it. For example, consider removing 20 from the tree below on the left. The largest value in 20's left subtree is 15, so 15 replaces the 20 at the`current`node, as shown on the right.You can get the largest in

`current`'s left subtree using the method`getLargestIterative(Node n)`that you already wrote.Copying the 15 into the

`current`node eliminates the 20, but now we have an extra copy of 15, one of which we must eliminate. It is easy to remove the 15 in`current`'s left subtree, because it is the largest value in that subtree and you have the method`removeLargestIterative(Node n)`that you wrote earlier in the lab!

There are 5 bonus points available in the `main` method of
`TestBinarySearchTree` that are to support removal of the root of
the tree. No need to worry about those until everything else is
working.

Submitting

Your submission requires that all required deliverables are committed and pushed to the master for your repository's origin on GitHub. That's it! If you see everything you intend to submit when you visit your repository's page on GitHub, you're set.

Grading

This assignment is worth 85 points, which are distributed as follows:

> Feature | Value | Score |

Lab Question 1 | 2 | |

Lab Question 2 | 2 | |

recursive sum | 5 | |

recursive numLeaves | 5 | |

tests for sum and numLeaves | 2 | |

recursive contains | 6 | |

recursive numAs | 6 | |

recursive getSmallest | 5 | |

tests for contains, numAs and getSmallest | 3 | |

Passing tests in TestBinarySearchTree | 49 | |

Bonus tests in TestBinarySearchTree | (5) | |

Total | 85 | |