Lab Check-in 3: Trees

Q1: To Tree or Not to Tree

Say you have some function defined as follows:

>>> def sum_tree(t):
...     """Computes the sum of all the nodes in a tree"""
...     if is_leaf(t):
...         return t
...     else:
...         return t + sum([sum_tree(b) for b in branches(t)])

Does this work? Why or why not? Some key points to think about:

• What type of data are we trying to return?
• Are we passing in the correct type of data into sum_tree in each recursive call?
• What kind of data is t?

Solution: This doesn't work because sum_tree returns a number, but the base case returns t, which is a tree. Therefore, [sum_tree(b) for b in branches(t)] will return a list of trees, and calling sum on that list will break. Also, the recursive step attempts to add t to something else, but t is a tree, and it cannot be added to something else with the standard + operator.

When defining recursive functions you should:

• (almost always) Return the same type of data at each point in the program. For example, don't return 3 in one of the base cases if you're returning True or False in another base case). There are exceptions, but they don't happen often
• (always) Pass in the correct type of data every time you call a function. For example, do not pass in a number into sum_tree above because the function takes in a tree.
• (always) When making the leap of faith, keep the format of the data in mind, even if you don't know what it is. In sum_tree, you don't know exactly what each sum_tree(b) is, but you trust that each sum_tree(b) is a number representing the sum of all nodes in a particular branch, and therefore [sum_tree(b) for b in branches(t)] is a list containing the sum of all nodes in each branch. With that in mind, you're able to call sum on this list of numbers and add it to the current label(t). This is important for later questions that are nearly impossible to do without trusting the recursion.