Impression of Week 6

    This week, we met a new class - Tree. And we are implementing a huge amount of recursions inside this class. This class is basically nested-list inside nested-list but in the form of  nodes and children. So whatever we are going to de with the tree, we have to go over every node and its children and this is where recursion fits in.
    In the lecture, we did the function contains which is used to check if a number is in a tree.
    To implement contains, first we start with simple tree which is just a leaf with no children. We check if the root value is equal to the given value. And now we have the worst part of the function:
            def contains(t, v):
                  if len(t.children) == 0:
                      return t.children == v
                  else:
                        ...
    Now the question is what if the tree has children and its children have children? Recursion!
    The thought is, we have to check every node to see if its root value is v and check if v is in its children or children's children until we find all the leaves and check all of them. Checking a leaf needs the same code as in the if statement we just implemented checking a node needs the code to check its children and its own value. As the function will return a list of boolean outputs, if v is in the tree, at least one True should be in the list. Now we have the code:
                 else:
                       return t.value == v or True in [contains(c, v) for c in t.children]
    Also, we can make the function contains a special function __contains__. By doing so, running the function would be using 'in'.
           >>> t = Tree(3)
           >>> 3 in t
           True

    On Wednesday, we did a recursion called leaf_count which has basically the same idea. If the tree we are checking has no children then it is a leaves, so return 1. If not return nothing.
Here's the code:
             def leaf_count(t):
                   if t.children == []:
                        return 1
                   else:
                         return sum([leaf_count(c) for c in t.children])