Designing Data for Trees in Python

Code along video

Learning objectives

In this code along, we will start working with evolutionary trees by deciding how to organize the data that represent a tree. Our first idea will turn out to be redundant, and our second idea will introduce us to a recursive class declaration, along with a few of Python’s quirks.

Code along summary

Setup

Create a new directory python/src/trees and add a new main.py file there containing the following starter code.

def main():
    print("Organizing data for trees.")

if __name__ == "__main__":
    main()

Idea 1: nodes, edges, and trees

A tree is a collection of nodes connected by edges. The nodes at the bottom of the tree (the leaves) represent present-day species, and the other nodes represent ancestral species; the fancy word for any of these is taxon. The edges represent hierarchical relationships between nodes.

A natural first idea, then, is to declare a Tree dataclass with two attributes: a list of nodes and a list of edges. Since a Tree refers to Node and Edge, and Python reads a file in order, we need to declare Node and Edge above Tree. A node gets a label (the name of the species) and an age, which will be 0.0 for a present-day species and which our tree-building algorithm will infer for ancestral species. An edge connects a parent node to a child node. Add the following to the top of main.py.

from dataclasses import dataclass, field

@dataclass
class Node:
    label: str = "Unlabeled"
    age: float = 0.0

@dataclass
class Edge:
    parent: Node
    child: Node

@dataclass
class Tree:
    nodes: list[Node]
    edges: list[Edge]

Let’s construct a small tree in main() with two nodes and a single edge connecting them.

def main():
    print("Organizing data for trees.")

    n1 = Node(label="A", age=5)
    n2 = Node(label="B", age=10)
    e = Edge(parent=n1, child=n2)

    t = Tree(nodes=[n1, n2], edges=[e])

    # ...

    # we realize that I need to change some attribute of the tree
    # let's change its first node
    t.nodes[0] = Node(label="A*", age=0)

    print(t.nodes[0])
    print(t.edges[0].parent)

Navigate into python/src/trees and run python3 main.py. We see that t.nodes[0] changed, but the parent of the edge is still the original node.

Organizing data for trees.
Node(label='A*', age=0)
Node(label='A', age=5)

These should refer to the same node, but they don’t. The bigger problem is that our data design is redundant, which we have seen before with shapes: storing the area of a rectangle alongside its width and height would force us to remember to update the area every time the width or height changed. Here, a node is stored both in the list of nodes and inside the edges, and when we update one copy, the other falls out of sync. In object-oriented programming, minimalism is king, and so we want to represent a tree with as few attributes as possible. Let’s place idea 1 inside a docstring and keep it around as an example of what not to do.

Idea 2: storing edges recursively

A cleaner way to represent a tree is to eliminate the Edge class entirely. Instead, each node will store references to its two children, so that the edge relationships live inside the nodes. A tree is then just a list of nodes.

Since a list is mutable, we cannot just give nodes a default value of [], or else every tree would share the same list. Recall from our work with dataclasses that we instead use field(default_factory=list), which gives each new tree its own fresh empty list.

@dataclass
class Node:
    label: str = "Unlabeled"
    child1: Node
    child2: Node

@dataclass
class Tree:
    nodes: list[Node] = field(default_factory=list)  # fresh empty list for each tree

This declaration is recursive because child1 and child2 are attributes of a Node whose type is itself Node. Unfortunately, when we run this code, Python complains before main() even starts.

TypeError: non-default argument 'child1' follows default argument 'label'

You may also have expected a different error: how can we use Node as a type while we are still in the middle of declaring Node? In older versions of Python (3.13 and earlier), this produces NameError: name 'Node' is not defined. The fix is to place the type in quotes, as in 'Node', which tells Python to store the annotation as a string for now and make it into a Node after the declaration is finished. (Starting in Python 3.14, which is the version used in the video, Python postpones evaluating annotations automatically, which is why the video never shows the NameError. We will keep the quotes so that our code works in older versions too.) After making both changes, our Node declaration looks like this, and Python accepts it.

@dataclass
class Node:
    child1: 'Node'  # store as string for now, and then after declaration make Node
    child2: 'Node'  # store as string for now, and then after declaration make Node
    label: str = "Unlabeled"

Now let’s declare a node in main() for a present-day species, the axolotl. A present-day species is a leaf of the tree, so it has no children.

n = Node(label="Axolotl")
print(n)

Running this code produces another error.

TypeError: Node.__init__() missing 2 required positional arguments: 'child1' and 'child2'

Python is waiting on us to tell it what the two children of our axolotl are. What should a default child be? If we tried a default of Node(), then that default node would itself need two children, each of which would need two children, and so on; we would have only kicked the can down the road and created an infinite recursion. In some languages, this issue is handled by something called a pointer, which can be left empty when it does not point at anything. Python does not have pointers, so we instead say that a child’s default value is None.

But None is not a Node, and so we also need to tell Python that each child has type Node or None, which we write as 'Node | None'. Here is our final Node declaration.

@dataclass
class Node:
    child1: 'Node | None' = None  # store as string for now, and then after declaration make Node (or nothing at all)
    child2: 'Node | None' = None  # store as string for now, and then after declaration make Node
    label: str = "Unlabeled"

Now our code runs, and we see that the axolotl has no children.

Organizing data for trees.
Node(child1=None, child2=None, label='Axolotl')

If we want to connect nodes, it is just a matter of setting children. Let’s create an ancestor node and set its first child to be the axolotl.

vx = Node(label="Ancestor")
vx.child1 = n
print(vx)

Node(child1=Node(child1=None, child2=None, label='Axolotl'), child2=None, label='Ancestor')

The printed result is hard to read, but it shows that the ancestor’s child1 is the axolotl and that its child2 has not been set. We will need better ways of printing trees, and we will see one in a later code along. Finally, now that every attribute of Node has a default value, the order of the attributes no longer matters. When we implement our tree-building algorithm, we will list label first and give each node an age attribute as well.

Looking ahead

We now have a recursive Node class and a Tree that is simply a list of nodes. Before we implement an algorithm to build trees from biological data, the next lesson will walk through how that algorithm, called UPGMA, works.