Week 8 of CSC148: Assignment 2, LinkedLists, and Other Recursive ADTs

If I had to pick one word to summarize the last few weeks of CSC148 I would, without a doubt, pick the word "trees". All of the recent labs, assignments, exercises (E3 was just posted and, from a quick glance, looks like it involves tree traversals), and lectures have had to do with trees or some tree-related data structure, or more specific, nested ADTs like LinkedLists. Therefore, it seems only fitting to discuss the topic a little bit this week. Since linked lists are essentially just trees with an arity of one at every "branch" the same realm of logic applies throughout.

An important part of understand trees (or Trees, to be more accurate as were talking about a Python class), is understand tree traversals. There is pre-order, in-order, and post-order traversal, 3 algorithms which involve "visiting" the node before "moving" left then right, visiting it after going left but before going right, or visiting it after going both left and right, respectively. In exercise three we are required to take a in-order and pre-order traversal list and produce the corresponding tree, which is what I'm starting to think about now.

A part I have found interesting about nested structures while working with them so far is that their methods are often much more simple and elegant than you think their implementation might be like at first glance. I experienced this head-on in the last lab where we were required to write a few functions for the LinkedList ADT. My partner Brian (check out his great SLOG here) and I had gone the iterative route when designing our functions, only to realize later that our clunky code was much longer and more complicated than the recursive alternative to tackling the problem. It was definitely a good lesson, though. Another thing we realized, and something I had noticed on the assignment 2, was that often-times when dealing with linked structures like Trees (whether binary or not) you can find yourself writing recursive functions without even realizing. For example, if you write an __eq__ method for a Tree class, one option is writing it out as so:

return (self.value == other.value) and (self.child == other.child)

I hadn't noticed it at first, but by writing out this method I had written a recursive function. Since in many cases the child may be another Tree, the __eq__ will call itself again, and this will continue all the way until child refers to None in both. I found this very interesting.

Back to finishing up assignment 2 and time to start exercise 3!