Donation Trees
Goals
• Implement a BST
• Use the BST to solve a problem
Part 1
In the starter code, you have been provided with the definition of a class for a Binary Search Tree as well as a BSTNode. Implement the methods that you find within it. If you are confused about what a particular method is supposed to do or what a value means please post it on CampusWire
While you must write finish at least the functions provided you are free to add more functions if you would like. I certainly did in my solution.
Unit Testing
You need to write sensible unit tests using Python’s unittest module
You must test at least the following methods of your tree class
• __ init __
• get_min_node
• get_max_node
• add_value
• remove_value
• height
• __ len __
To help you test I have provided you with the definition for == between two trees. I have also defined __ iter __ for your BSTNode class as BST.__ eq __ depends on it to work correctly. No need to add any code to these functions.
We will be looking over your test cases to see if they make sense and test your code thoroughly. Please do your best to make this section of code as readable as possible because if we can’t understand it we can’t give you credit.
Mimir Testing
I will be running my own set of unit tests on your BST to verify that it is working correctly.
Locations and Names of Files and Folders
You are free to add more files and directories to your project but you cannot more or rename any of the files in the starter code.
Part 2
In Part 2 you will be using your BST to answer some questions about donors and how much they have donated.
Your program will be given a donors file which has the following format
Donor Name : Donation Amount. All donors will be unique in the file but multiple donors may have donated the same amount.
Your program must accept the following commands
• all: Print all of the donors from the smallest donation amount to the largest donation amount
• rich: Print out the donor who donated the largest amount
• cheap: Print out the donor who donated the smallest amount
• who: This command takes an additional argument
• who amount: Prints the first donor that who donated amount if any
• who +amount: Prints the first donor that donated at least amount if any
• who -amount: Prints the first donor that donated no more than amount if any
Examples
Assuming that donors10.txt contains
3 : 1142
9 : 354
5 : 6020
0 : 6335
4 : 2750
1 : 6941
6 : 3913
7 : 8422
8 : 9608
2 : 7726
Then python3 donor_runner.py donors10.txt all prints
9 with a donation of 354
3 with a donation of 1142
4 with a donation of 2750
6 with a donation of 3913
5 with a donation of 6020
0 with a donation of 6335
1 with a donation of 6941
2 with a donation of 7726
7 with a donation of 8422
8 with a donation of 9608
python3 donor_runner.py donors10.txt cheap prints
9 with a donation of 354
python3 donor_runner.py donors10.txt rich prints
8 with a donation of 9608
python3 donor_runner.py donors10.txt who 100 prints
No Match
python3 donor_runner.py donors10.txt who 6020 prints
5 with a donation of 6020
python3 donor_runner.py donors10.txt who +6100 prints
0 with a donation of 6335
python3 donor_runner.py donors10.txt who -6100 prints
5 with a donation of 6020
Input
• Input will be given through command line arguments.
• All input will be valid.
Creating More Donor Files
You will find a program called donor_builder.py that will create sample donor files for you. You can use it to help out with your testing.
Running The Program
On Mimir, your program will be run as python3 TreeProblem/donor_runner.py. This means that you should place the starting point of your donor program in donor_runner.py.
Submission
Your submission must have the same structure as the starter code. When submitting zip the TreeProblem folder. You are free to add more folders and add more files but you can NOT remove, move, or rename any of the folders and files in the starter code. Doing so will break the testing and you won’t receive any credit for your submission.