Week 6

This weeks' series of lectures was based are trees, which can be used as a visual representation of data.
.

The parts of this tree, called nodes, can be described with more specific terms;

The node that serves as the spawning point for other nodes is called the root. ie: 8
A leaf is describe as a node with no children; it is the end of the path. ie: 1,4,7
The 'middle' nodes are internal nodes, such as 3,6, and 10.

Trees can be analyzed through another subject we have learned; recursion. As an example, lets say we want to count the number of nodes in this tree. We can create a count function such that

def count(t: Tree) -> int:

    """How many nodes in this Tree?

    >>> tn2 = Tree(2, [Tree(4), Tree(4.5), Tree(5), Tree(5.75)])

    >>> tn3 = Tree(3, [Tree(6), Tree(7)])

    >>> tn1 = Tree(1, [tn2, tn3])

    >>> count(tn1)

    9

    return 1+ sum([count(c) for c in t.children])

 

In this example we use recursion to access and count the nested lists (aka  the children) of the tree. We are able to count all the nodes using this method. The reason recursion is so useful is because a tree often presents multiple paths leading to multiple ends. Through recursion however we can account for all these paths, and come to conclusions based on the whole picture.