Homework 8
Removing in a Binary Search Tree

Due: Tuesday, March 29, 11:59pm

The files you may need for this assignment can be downloaded from the schedule page. A makefile is available here.

Collaboration Policy

For this assignment, you may work with a partner. If you do, please submit only one version of the files, and clearly include your names and a discussion of the workload distribution in your readme.

Please make sure you adhere to the policies on academic integrity in this regard.


Overview and Task

For this assignment, you must implement the remove method for the Binary Search Tree class. The general idea was covered in class, and you may refer to lecture notes or the text book for assistance.

To implement remove, you will first use the find function to see if the value is in the list. If it is, there are several cases to consider.

Say that your value is in node x. If x is a leaf, you can simply delete it (using helper functions from BinaryTree.h). If x has only 1 child, you can delete it and promote that child while maintaining a binary search tree property. However, if it has two children, you need to find the next node in an inorder traveral. Call this node y. If y is a leaf, you swap the value into x's position and then delete the leaf node that contained y. If it is not a leaf, it must have only a right child (since the left child would come first in an inorder traversal), so you can delete y, promote its right child, and still put y's value into x's node.

For this assignment, you are welcome to implement any helper functions you need - just be careful to put them in a protected or private setting if they are not something an end user should have access to. More likely, you will want to use the functions provided in BinaryTree.h, both for the tree and for iterators.

Note: For simplicity, we are assuming that your trees will only store distinct elements. So if a value is inserted twice, you do not need to have it represented twice in your tree. You DO need to handle this case without crashing, however!

Debugging Your Program

Write a function called TestBST.cpp which creates a binary search tree and performs inserts and removes on the tree. You are welcome to use the draw function (inherited from BinaryTree.h) to draw your tree at each step and debug your code. Note that you should do fairly exhaustive testing here - make sure you handle all possible cases, including those that involve the root, leaves, etc., which are commonly left out of testing.

Again, feel free to write other test functions - such as a function that prints the height of a node, or an inorder traversal of the tree - if that is helpful for your debugging process.

Files We Are Providing

All such files can be downloaded from the schedule page, except the makefile, which you may download here.

Files to Submit

Grading Standards

The assignment is worth 10 points. Your readme is worth a half point. Part of the readme expectation beyond the usual discussion of your implementation is that you also discuss and justify that you have done fairly exhaustive testing to be sure no cases are missing, particularly those that are likely to cause segmentation faults. Your test file will be worth 2 points. The remaining 7.5 points will be given for working remove code in the Binary Search Tree class.