Week 10: I will find you, but I won't kill you

The strike has been going on for three weeks. Thus, we have not had labs or quizzes for the past three weeks. They are worth 10% of everyone's final CSC148 grade. My TA was quite helpful with the lab exercises because I could not do the labs on my own. I still can't do them on my own. While the strike has been going on, I started turning to Piazza or office hours to ask questions. Nevertheless, Professors Heap and Horton have been doing a great job with managing the course, office hours, and Piazza discussions while the TAs are gone, so hats off to them!

In this post, I am going to talk about mutating binary search trees using recursive functions insert() and delete() in class BTNode.

All of the following conditions must be present for a tree to be classified as a binary search tree:

1. All data are comparable.
2. Data in the left subtree are less than root.data.
3. Data in the right subtree are greater than root.data.

Here is a visual representation of a binary search tree.

I found the lecture on mutating BSTs straightforward to follow. In the additional exercises for Lab 6, the insert function can be found, and the code implementation is based off the general formula for recursion: base case, then general case.

To implement insert, we need an accumulator variable as our return value. Next, we start with the base case: if the node is a root, we create a leaf using a variable. Then we look at conditions 2 and 3 from above. If the data in the left subtree are less than root.data, recursively insert new data in the left subtree. On the contrary, if the data in the right subtree are greater than root.data, recursively insert new data in the right subtree. Finally, return the accumulator variable.

As for the delete function, we looked at an algorithm to help us implement it together in lecture. It is very similar to the algorithm for insert, except we recursively remove data in either the left or right subtrees in this case. However, there are a few extra steps. 

"I'm overwhelmed already," I think to myself as I attempt to understand how it works.

If a node with data has less than two children, acknowledging that one of the children is None, return the other child. Finally, if a node with data has two children that are not None, then replace that data with the largest child in the left subtree. Delete the original data that was swapped with the new data, and then return the new data.

I'm definitely going to practice with these two functions in Lab #8 while balancing work from my other courses.

This is the code that Prof. Heap showed us and had us work with.

I wish everyone the best of luck in A3 and the rest of the course! It's not easy, but it's not impossible! I'll leave you all with some motivation because positivity is key.