Week 8: Oct 28 - Nov 3

This week the class explored one of the uses of a tree: a binary search tree. By putting all values below the root node as the left subtree, and all the values greater as the right subtree, a binary search can be performed much more efficiently than if the values were simply in a sorted list (you would still have to constantly find the middle value in a sorted list). Of course, there is the added complexity of actually adding the values into a binary search tree, but assuming that you start from an unsorted list, it should take around the same time to add values into a tree from a list as it is to sort the list. All of the binary search trees were constructed using linked nodes, the concept of which was explored last week.

The lab and exercise this week both demonstrated how binary trees work. Though the process of searching through and inserting elements into a binary tree, as well as other operations such as finding all values less than a given value (which was the topic of the lab) are all best done recursively, step 4 of the lab demonstrated that, by using a stack data structure to store nodes, it is possible, though much more difficult, to create an iterative way of searching through a binary search tree. The exercise, though simple (most of the code required is given, and only about 5 lines were added in both part A and B), it reinforced the way that a binary tree operated.