Week 6: Tree

So this week we learned what's tree, how to construct a tree recursively and how to use tree to store data.

Generally speaking, tree is an abstract data type that simulates a hierarchical tree structure, with a root value and sub-trees of children, represented as a set of linked nodes. Also, a tree can be defined recursively as a collection of nodes (starting at a root node), where each node has a value, together with a list of "children" nodes. Tree is very useful and convenient, since a tree can be analyzed mathematically both by nodes and as a whole.

Recursion is what we use to construct a tree. Since every tree is constructed by nodes (or sub-trees), we can set the root node as the base case of the tree. Thus we define what a node is in the __init__ function. And when we build a tree, we can keep add new nodes as children to the root node. Since the tee is constructed by recursion, when we need to get all data from the tree, we need to use recursion to get the data, and thus we have pre-order, in-order and post-order (we get data node by node). Similarly, when we define tree methods, recursion is used (since every method is supposed to work on a tree which's built recursively).

In my opinion, tree its self is not a challenging concept, but the recursion under it is. It's not easy to point out what's the base case and how to build recursion step when I first met the concept. However, I found it very helpful to use structural proof (what I learned from CSC240) when I work on recursion problems. Root node is the base case, and the children are constructed by induction ( recursion) steps. And tree methods are supposed to work on the whole tree (both root and children). This is super similar with the structural proof ( Prove a proposition works both for the base case and the induction), but the difference is that this time we are not asked to prove certain arguments, instead, we are asked to find a method which works for the entire. However, the idea is same.