Week 6 - Tree Traversals, Recursion with the Tree ADT

    Hi there! This week's post is going to be about traversing the tree data structure. When I think about the tree data structure, I think about a more detailed version how you may draw a tree as a young child, or a family tree diagram. You would start with a leaf and then put two 'branches' below it, with each branches containing another leaf that has two branches (it doesn't have to be just two branches, it can vary). In computer science, we say that a node (like a leaf in real life) is something that contains a value and possibly some labels pointing to its children (similar to a leaf having branches with other leaves attached to the end of them). The superseding node of a given node, if it exists, is known as the root, or the parent node. You can think of the tree ADT as a series of smaller sub-trees connected to each other such that there are no paths that form loops (or cycles).

There's a lot more terminology that I can go through, but I believe that it wouldn't be difficult to understand what I'm about to explain: the tree abstract data type (ADT). Every node in a tree has a cargo, which contains some sort of data, and labels or links to other nodes. Sometimes, other nodes can be the roots of other trees - nested trees. We've also learned about methods of traversing trees - pre-order and in-order traversal. When traversing a tree of integers to find a sum of all of them, we could use recursion by using 0 as the base case if there isn't a tree on the left or the right of any given tree node. For example, given a method called sum, and some TreeNode class that has instance variables, left, right and cargo; we can find the summation of all of the cargo given that the cargo of each node is some integer. We add sum(tree.left), sum(tree.right) with the tree's cargo given the base case that if the tree is None, we return 0. Whenever you are done traversing the tree completely on the left with sum(tree.left), you are left with '0 + 0 + tree.cargo' where tree.cargo is some integer. And you keep returning it to the recursive caller, so the effect is that you keep adding tree.cargo for every tree (interesting, right)?

I feel that we are now becoming more like computer scientists. I could only imagine that we are approaching searching algorithms to ADTs, such as depth-first search - this course will only become more interesting...

Until next time,

GR