Code along video
Note that the livestream pauses for a few minutes while Phillip updates the starter code, so you can skip ahead from 43:35 to 48:05 in the video.
Learning objectives
In this code along, we return to our implementation of UPGMA and use recursion to write the one remaining method that it needs, count_leaves(). We will see that trees are a context in which recursion is far superior to any other approach.
Code along summary
Setup
We will continue working in the upgma directory, this time in datatypes.py and main.py.
A sample tree
Throughout this lesson and the next, we will work with the following small tree with three leaves, A, B, and C, which we assume was produced by UPGMA. The leaves have age 0, the internal node internal1 has age 3, and the root has age 4. Each edge weight is the difference between the ages of the nodes it connects, so the edges from internal1 to A and B have weight 3, the edge from the root to C has weight 4, and the edge from the root to internal1 has weight 4 – 3 = 1. Let’s copy this picture into a comment at the bottom of main.py.
# Sample tree # # root (age=4) # / \ # (1) (4) # / \ # internal1 (age=3) C # / \ # (3) (3) # / \ # A B
Trees are recursive
We have already seen recursion in our work with trees, even if we did not call it by that name. Recall that every Node has a label and an age, and rather than storing a collection of edges, each node stores references to its two children, whose type is itself Node (or None, if the child does not exist). This makes the declaration of Node recursive.
The one function that we still need to run UPGMA is the Node method count_leaves(), which returns the number of leaves in the tree whose root is the current node. In our sample tree, the answer is 3 if we are at the root, since A, B, and C are all beneath us, and it is 2 if we are at internal1. If we are at a leaf, the answer is always 1, since the only leaf beneath us is ourselves.
The leaf is our base case. If we are at an internal node, then we delegate the work to two minions, our two children: the number of leaves beneath us is the number of leaves beneath our left child plus the number of leaves beneath our right child. We might have a thousand leaves beneath us or only two, but this idea works regardless. And unlike our Fibonacci function, this recursion never repeats any work, since the left child only considers its own subtree, and the right child only considers its own subtree.
Counting leaves
Open datatypes.py. In our base case, we check whether we are at a leaf by calling another method, is_leaf(), which we will write in a moment. (We are practicing structured procrastination!) In the inductive step, we start a count of leaves at zero, and then we add in the number of leaves of each child that exists. We use two independent if statements, since an internal node usually has both children. Each check makes a recursive call to count_leaves() on a child.
def count_leaves(self) -> int:
"""
Count the number of leaf nodes in the subtree rooted at this node.
"""
# base case: I'm at a leaf, in which case return 1
if self.is_leaf():
return 1
# inductive step: I have at least 1 child
# if the left child exists, add its # of leaves
# if the right child exists, add its # of leaves
leaves = 0
if self.child1 is not None:
# do have a left child, and add its leaves into total
leaves += self.child1.count_leaves()
if self.child2 is not None:
# I have a right child, and add its leaves
leaves += self.child2.count_leaves()
return leaves
Now for is_leaf(). A leaf is a node at the bottom of the tree, which means that if we try to access its two child references, we will find that both of them are None. If that is the case, we return True; otherwise, we have at least one child, and we return False.
def is_leaf(self) -> bool:
"""
Method that returns true if given node is a leaf and false otherwise.
"""
# we are at a leaf if both child references are None
if self.child1 is None and self.child2 is None:
return True
# we have at least one child reference to a Node, so I'm not at a leaf
return False
Note: Depending on when you downloaded the starter code,is_leaf()may already be written for you indatatypes.py. If so, compare it against the version above.
Testing count_leaves()
A function this short can seem too good to be true, so let’s test it on our sample tree. In main.py, add from datatypes import Node to the top of the file, and then build the sample tree in main(). We create the three leaves, and then we set the children of internal1 and root. Remember that child1=leaf1 does not make a copy of leaf1; it makes child1 reference the node that we already created, which is exactly what we want. We don’t need to set ages yet.
def main() -> None:
print("Happy trees.")
leaf1 = Node(label="A")
leaf2 = Node(label="B")
leaf3 = Node(label="C")
internal1 = Node(child1=leaf1, child2=leaf2)
root = Node(child1=internal1, child2=leaf3)
print("Total number of leaves:", root.count_leaves())
print("Number of leaves in the tree whose root is A is", leaf1.count_leaves())
print("Number of leaves in tree with root internal1:", internal1.count_leaves())
Navigate into python/src/upgma and run python3 main.py. We see that our method gives the correct answer in each case.
Happy trees. Total number of leaves: 3 Number of leaves in the tree whose root is A is 1 Number of leaves in tree with root internal1: 2
Earlier in the course, we introduced recursion as yet another way of solving problems like summing integers, for which a loop or a formula works just as well. Trees show us that in some contexts, recursion is the vastly superior approach. Any time that we want to know something about the tree beneath a node, we can ask each child for the answer about its own subtree and then combine the two answers.
Looking ahead
With count_leaves() written, our implementation of UPGMA is complete. But once we have built a tree, how do we look at it? In the next code along, we will use recursion again to convert a tree into a standard text format that other software can read.