Week 9

Week 9 – Binary trees

So this week was Binary tree week!

These trees aren’t too different from regular trees, the only differences is that each node has two children, hence the name binary. Another fun fact, the child on the left of each node is always smaller than the root node, and the child on right is always bigger. In a way, this makes them simpler to use and search through than regular trees. This picture is a pretty good representation of a binary tree:

And that’s another thing we did this week! We worked on how we would search through binary trees to find, insert or delete values. Since Binary trees are more structured, all we need to do is compare our value to the root’s value, and if it’s larger, then we go to the right, otherwise we go left, but if it’s the same then we know to stop. By using recursion to search through the tree, and by using this form of Binary search, we actually don’t need to go through almost half the list, and this makes our program much more efficient since it cuts down the runtime as well, to about O(lg n) where n is the size of the sorted list.

We also reviewed the other sort methods seen in 108, such as Selection sort and Insertion sort, and compared their runtime. Thanks to CSC165, calculating runtime and Big O wasn’t a new concept to me and I’m actually quite familiar with it, which made this week’s material easier to understand.

 

Lab 8

I found this week’s lab was pretty interesting. We basically just got a bit of practice working through binary trees and binary tree node functions. My partner and I had to write the recursive function count_less to count how many nodes had values less than the given argument. However, we had to implement it in different ways for example, either by adding a nested helper function or a helper method. I found it pretty confusing at first since I’m not used to writing nested helper functions and working with Binary trees, however, after getting through step-one, the rest of the steps were pretty similar and didn’t take much work. And of course, recursion practice is always good!