CSE 100 PA1: BST in C++
Pair Programming Partner Instructions
If you wish to work with a partner, please be sure to read the guidelines for Pair Programming in the syllabus carefully. Make sure to have both of the partners’ names on the headers of all files. Most importantly, make sure to submit your homework on Gradescope using only ONE of the accounts and do not forget to add the other teammate’s account into the submission.
Academic Integrity and Honest Implementations
We will hand inspect all submissions and will use automated tools to look for plagiarism or deception. Attempting to solve a problem by other than your own means will be treated as an Academic Integrity Violation. This includes all the issues discussed in the Academic Integrity Agreement, but in addition, it covers deceptive implementations. For example, if you use a library (create a library object and just reroute calls through that library object) rather than writing your own code, that’s seriously not okay and will be treated as dishonest work.
Retrieving Starter Code
To retrieve the starter code, go to this page. (If you have accidentally cloned starter code before Jan. 9th, make sure you re-download the latest starter code) :
Copy the git url of your repo from here after clicking “Clone or download” (make sure the URL you copied starts with https):
Then on your own machine or on ieng6 you can clone the repo like this:
Now go back to GitHub and create your own private repository.
Now cd into the PA1 starter code repository you cloned earlier. Type “git remote -v”.
We’re going to remove the remote called origin, so we can then add your own GitHub repository as the new remote called origin: run “git remote remove origin”
If you now run “git remote -v” you should no longer see the remote called origin like you saw before. Now run the commands listed on your newly created git repo (be sure to replace the url in the screenshot below with the url to your repo).
(If your terminal did not ask you to log in upon executing this git clone command, double check that the repo is set to private.)
You should now see the PA1 starter code on your private GitHub repository. If you are working with a partner, add them as a collaborator on your private repository. First click the settings tab on your GitHub repository.
Then click Collaborators on the left and search for your partner’s github account.
Among the starter code files, only the following files are relevant to implementation and testing. You are required to only implement the underlined files, and you must leave all the other files unchanged, especially “main.cpp” and “mainInt.cpp”
In src/bst folder:
In test/bst folder:
In data/mainInput folder:
In data/mainIntInput folder:
In the top level folder:
To complete the assignment, you will modify the files in the starter code to provide full definitions for methods marked with // TODO. To see all of the TODO tags, you can run the command “grep -r TODO .” in your PA1 directory.
We personally recommend using grep like this as you can manipulate the arguments after “A” and “B” to get a good snapshot of what is required: grep -r -A 5 -B 5 TODO *
To search in VSCode, you can also use Ctrl+Shift+F or Cmd+Shift+F on mac
You can find all the relevant information about compiling your code and running tests in the README.md file of the starter code.
Submitting Your PA
You will be submitting your code using Gradescope through the Github submission option. You should have gotten enrolled in Gradescope by now (if not, please add your name to the appropriate piazza post ).
Instructions to submit your PA on Gradescope:
- Be sure to test your code on ieng6 or in the devcontainer. We will be grading your code on the same environment as ieng6 and the devcontainer. There may be issues with compilers/etc if you only tested your code on your personal machine outside of a devcontainer using self-installed dependencies.
- Be sure to push the final version of your code to your private Github repository. (That will be the code you will submit if you are submitting using Github)
- Go to gradescope and find PA1 checkpoint/final submission. You may use either Upload or Github to submit.
Upload: In the root directory of your PA1, run ./create_submission_zip.sh. The script will create a zip file named submission.zip, then simply drag the zip file to gradescope to finish the submission. It is very important that you use the submission script to generate zip file rather than uploading the entire directory, as some PA will contain files that are quite large.
Github: You will be asked to authorize your GitHub account if you haven’t done so before. After authorizing your account, choose the repo you pushed your final version of PA1 code to and the correct branch.
- Check the feedback from the autograder and make sure no compile errors appeared.
- If you are submitting with a partner, make sure that the student who submits adds the other student to the assignment.
- You can submit as many times as you like before the deadline: only your last submission will be counted.
Checkpoint Submission (Due Thursday, Jan. 16th, 11:59 pm):
When you have completed all of the requirements for the checkpoint submission (Part 1, everything except rebalance and delete). You should go to gradescope and find PA1 checkpoint submission. Only the files in your src and test folders will be graded.
Make sure your code can compile (running ‘meson build’ and ‘ninja -C build’ in project directory gives no error)
Final Submission (Due Thursday, Jan. 23rd, 11:59 pm) :
When you have completed all of the requirements for the final submission (All the parts). You should go to gradescope and find PA1 final assignments: PA1 Final Submission and WorkSheet.
Only the files in your src and test folders will be graded.
Make sure your code can compile. (running ‘meson build’ and ‘ninja -C build’ in project directory gives no error)
Please follow the style guidelines below on course website.
When grading the PAs, there won’t be points specifically allocated for style, but bad style will result in up to 10 points deduction from the points you get in the other parts. (Bad style includes magic numbers, missing method headers and lacking inline comments etc.)
You have an auto formatter available to you (check the Readme.md for details), use it!
Part 1 (Checkpoint): Implementing a Binary Search Tree in C++
In this part of the assignment, you will implement the fundamental BST operations using concepts from the C++ Standard Template Library, which includes writing an iterator for it.
- Understand the code and write unit tests
Your first task is to review the concepts about BST and understand the starter code. Do not attempt to start writing code until you have a firm grasp of what the provided code does and what you are supposed to do with it. You are required to implement all the methods with TODO in the header (except for the copy constructor and deleteNode method, which you will implement for the final submission), make sure you read the details of each method below (Part 1.2).
We will use the GoogleTest framework to perform unit tests. You should first read the README.md in the starter code to get introduced. Then make sure you can understand the provided incomplete test files in the test folder. (All the unit tests files have a prefix “test_”)
It is important that you add your own unit tests there before you start implementing any code of your own. Try to avoid “big bang development” where you first try to finish all the code and then find out nothing works as expected. Instead, try to locate the easiest unit of functionality you need to implement and start writing tests for its expected behavior. Then implement the expected behavior of that simple unit and verify it by running your tests. After you’ve confirmed it works as expected, make a git commit to save your changes and move on to the second simplest unit, and repeat the process.
We suggest you familiarize yourself with the GoogleTest framework by writing tests for methods and classes that are already completed in the starter code. It is also a good way to get to understand the workings of those methods and classes.
- Implement methods in BSTNode.hpp, BSTIterator.hpp, and BST.hpp
Please first read and understand the purpose of each member variable at the top of the file. Do not modify any public method signatures. You may modify the private helper methods or add any additional member variables if needed.
BSTNode(const Data & d)
Constructor. Initialize a BSTNode with the given Data item, with no parent and no children
Return the successor of this BSTNode in a BST. The successor of this BSTNode should have the smallest element that is larger than this BSTNode. The BST should be unchanged after the function call. If there is no successor, return nullptr. This method is used in the BSTIterator’s ++ operators to advance the iterator. Moving iterator from the first element till the end should give you sorted data in the BST.
Note: Try to analyze different cases of successor() by examining the successor of all the nodes in an arbitrary BST that you draw.
bool operator==(BSTIterator<Data> const& other) const
Equality test operator. Two iterators are equal to each other if they contain the same BSTNode pointer.
bool operator!=(BSTIterator<Data> const& other) const
Inequality test operator.
bool insert (const Data& item)
Given a reference to a Data item, insert a copy of it in this BST. Return true if the item was successfully added to this BST, false if an item equal to this one was already in this BST. This means the BST should not allow duplicate insertion. The average runtime of this function must be O(logn).
Note: This function should use only the ‘<‘ operator when comparing Data items. The reason for this is that some data types do not have the other operators (>, <=, >=, etc.) overloaded. For safety reasons, it’s best to only use < to compare. Remember: given an element, you need to check if it’s less than, greater than, or equal to element in the BST. How can you do that with just the < operator?
iterator find (const Data& item) const
Find a Data item in the BST. Return an iterator pointing to the given item, or pointing past
the last node in the BST (an iterator containing nullptr) if not found. The average runtime must be O(logn).
Note: This function should use only the ‘<‘ operator when comparing Data items for the same reason above.
unsigned int size() const
Return the number of items currently in the BST.
int height() const
Return the height of the BST. Note that empty BST has height -1 and BST with only one node has height 0.
bool empty() const
Return true if the BST is empty, else false.
iterator begin() const
Return an iterator pointing to the first item in the BST (the smallest element in current BST). Implement this method by completing the private helper method first(), which finds the first element of this BST.
vector<Data> inorder() const
Perform an inorder traversal of this BST to collect the data of each node in ascending order to a vector. Consider using a helper function to implement it. You should not use iterator or successor() in this function, we will manually check this in grading your PA.
Default destructor. Delete every node in this BST. Implement this method by completing the private helper method deleteAll().
Please read the Testing part below to understand how to test your code. You can also find the point distribution of this PA on that section as well.
By the time you submit PA1 checkpoint, please complete the following two surveys with each of them worth 1 point towards your PA1 checkpoint grade
Part 2 (Final Submission): Tree Balancing and Node Deletion
In this part of the assignment, you will extend your binary search tree implementation to add a few additional operations. The first is to balance a given BST, the second is to delete a single element from the BST.
- Understand the code and write tests first
First, read the requirements of each method below write unit tests to define and understand the expected behavior of the required functions.
- Implement methods in BST.hpp
Please do not modify any public method signatures. You may modify the private helper methods or add any additional member variables if needed.
BST(const BST<Data>& bst)
A copy constructor that creates a valid balanced BST with all the data in the given bst. This constructor should take one other BST, copy all its data and create a new set of BSTNodes to build a balanced version of that given BST. You may assume the current BST is empty (root is null) before the function call. The given BST should be left unchanged after the function call. You should implement this function by finishing the helper function buildSubtree().
Note: For a given set of data, there may be multiple valid balanced BST. However, for testing and grading purposes, your balanced BST from a given BST must be unique which follows the rule below:
For any subtree of the balanced BST, if the number of nodes in that subtree is even, there can be two median node within the subtree. In this case, you must pick the node with larger median data to be the root of the subtree. For example, if the given BST contains data 2,3,4,5, then the resulting BST should be:
It is important that you follow the rule above in your program to pass the tests in autograder. This means when given one arbitrary set of data, your balanced BST should be unique. If your function produce different balanced BST, you will not receive credits for this function.
BSTNode<Data>* buildSubtree(vector<Data>& data, int start, int end, int depth)
The helper function that recursively builds a balanced BST with the given data.
data: a vector of data used in building BST
start: the start index (inclusive) of the vector used to build the subtree
end: the end index (exclusive) of the vector used to build the subtree
Depth: the depth of recursion, used to update height
bool deleteNode(const Data& item)
Given a reference to a Data item, delete the copy of it in this BST. After the deletion, the BST should still be valid. Return true if the item was successfully deleted from this BST, false if an item equal to this one does not exist in this BST.
Note: There might be multiple correct ways to delete a node from a BST. However, for testing and grading purposes, your node deletion must follow the rules below in each case:
- Node to delete is a leaf node: Directly delete the node and no further modification of BST is needed.
- Node to delete has exactly one child: Connect the parent node to the child node and delete the current node.
- Node to delete has two children: Replace the current node’s data with its successor node’s data, and delete the successor node to avoid duplication.
It is important that you follow the rule above in your program to pass the tests in autograder. This means when deleting some elements in the BST, your resulting BST must be unique.
This function and all its helper functions should use only the ‘<‘ operator when comparing Data items for the same reason mentioned in insert() above.
Please read the Testing part below to understand how to test your code. You can also find the point distribution of this PA on that section as well.
When you submit your PA1 final submission, please complete this survey for your weekly reflection 2: https://forms.gle/CGB5t4hB9TBUtV7w7 . This survey is worth 1 point towards your PA1 final submission grade.
Part 3: Worksheet
Please print and complete the worksheet linked below. It will be submitted in pdf format as a separate assignment on gradescope. The worksheet is worth 5 points.
Note that the worksheet is an individual assignment, this means if you are working with a partner, you should not collaborate with your partner to finish the worksheet.