Week 8

Impressions of Week 7:

The main focus of week 7 in regards to the lecture material was an introduction to binary trees, an extension to the Abstract Data Type, "Tree" that we previously covered. At first, this concept seemed quite simple for me to grasp however when it came down to the logistics I quickly realized I needed to reorient my understanding toward how specific attributes (aka variables belonging to this new class) were being represented in Python. I will be using this approach to develop the groundwork needed for constructing algorithms that sort or traverse through this type of Tree design.

Class BTNode or Binary Tree node, defines a Tree consisting of data stored at a root node with either None, 1 or 2 children that are represented according to their "left" and "right" arrangement (i.e., self.left & self.right). For simplicity's sake, these left and right parameters within the __init__ method are set to None in order to quickly discover leaves within the Tree (which contain None for left and right branches). In addition, for Binary Search trees, data in the left and right subtrees are ordered such that  the left subtree is less than node.data and the right subtree is greater than the data at its respective node, making it much easier to sort through when searching for a desired value or object. The standard special methods __str__, __eq__ and __repr__ apply to these classes and function as a self-check for the design being developed as well as a user-friendly representation of what the computer is working with.

Part of the versatility of binary trees is that they can be used to represent arithmetic expressions in which no expressions are left empty, the value is returned for each leaf and data contained within the left and right trees is evaluated then combined using the binary operator contained within the root node. Thankfully, the built_in function 'eval' is designed to perform this algorithm.

Additionally, this was my first week being introduced to defining parameters as 'Type' function within the doctoring. In this case, every time the parameter is called, Python refers back to the function provided within the definition of the parent function. In combination with this new ability, 3 new recursive Tree traversals were briefly presented, including inorder, preorder and postorder, differing only in placement of the print statement with regard to two recursive function calls. For example, the preorder method visits the parent node prior to recursing through the left subtree and then the right while the postorder method starts off recursing through the bottom of the left subtree (calling on any right leaf before the node if 2 children are present) then through the bottom of the right subtree, visiting the node itself at the end. Lastly, the inorder method also begins by recursing over the left subtree but calls on the node itself prior to recursing over the right subtree. A visualization of these methods is provided below.

Source: http://rosettacode.org/wiki/Tree_traversal