Even though lists are recursive, we don't typically think of them as recursive because their linearity makes it very convenient to approach them iteratively. This is not the case for all recursive structures.
Recall that we can view lists as a pair of a value and a list. But what if we generalize this: instead of pairing a value with just one list, what if we had a value with multiple lists? Of course, this definition would carry on for those sublists as well. Such a structure couldn't be called a list anymore...
Trees are a fundamental structure in discrete mathematics and computer science. Informally, you can think of a tree as a node with a value and multiple nodes as "branches" (there are those multiple lists).
In general, trees are used to model hierarchical relationships and structures. For example, a document tree gives the outline of a document (sections, subsections, etc.). A phylogentic tree gives a representation of how species evolve and change. A parse tree encodes the grammatical structure of an expression.
From this description, it's not obvious that trees are a recursive structure. We will give the following definition.
A tree is
Notice the similarity between this definition and the one we had for lists.
The fact that a tree can be empty seems a bit strange, but it's no different from any of the other recursive definitions we've seen before. Meanwhile, a non-empty tree can be thought of as a node that anchors some subtrees.
Curiously, this node definition contains two other things: a value, which we expected, and a key. Strictly speaking, a key isn't necessary for a tree. However, for our purposes having a key has some nice conveniences for things like searching and visualization.
One can get special kinds of trees by restricting the number of children. For instance, a tree in which every node has exactly two subtrees is called a binary tree.
Unlike lists, trees are not a built-in data type in Python, so we will have to define our own. We have a few decisions to make. At the very least, we know that if a tree isn't empty, it needs to keep track of three things: a key, a value, and its subtrees.
We need to make a class for trees and the key, value, and children of the tree need to be attributes. The key and value is easy to take care of. Since our definition doesn't restrict the number of subtrees a tree can have, we can use a list.
However, we have another issue: we also need to represent empty trees. We will make the decision that if the key we store is None, then our tree is empty.
This gives us the following class definition.
class Tree:
"""
A class representing a tree. More specifically, an instance of this
class will represent either an empty tree or a tree with a node and
zero or more of subtrees.
"""
def __init__(self, key=None, value=None):
"""
Creates either an empty tree or a tree with a node and no
subtrees. The node contains a key and value.
Input:
key (Any): Key for node. If key is None, then an empty tree
is created.
value (Any): Value for node. If key is None, then value must
be None.
"""
assert key is not None or value is None, \
"Tree must either be empty (key and value both None) " \
"or it must have a key"
self.key = key
self.value = value
if key is None and value is None:
self.children = None
else:
self.children = []
Our constructor will take in two optional values: key and value. We make the decision not to specify children and instead add them later.
Currently, our constructor distinguishes between two cases: empty or not. Since we define an empty tree to have a key of None, we enforce the condition that if key is None, then all other attributes must also be None.
Then if the tree is non-empty, it must have a key. Notice that in this case value can be optional—if we don't want to use both keys and values, we can just use only keys. Then children is initialized to an empty list.
One thing that would be helpful to have is a way to determine whether the tree is empty.
def is_empty(self):
"""
Returns True if the tree is the empty tree, False otherwise.
"""
return (self.key is None and
self.value is None and
self.children is None)
So we can create trees like so.
empty_tree = Tree()
t1 = Tree("key")
t2 = Tree("key", "value")
Since we can't specify children when initializing the tree, we need to add them after creation. We do this with the add_child method, which takes as input a tree to be added as a child.
t1.add_child(t2)
The add_child is pretty straightforward (i.e. not that interesting): it just takes a tree and adds it to the children list.
The recursive structure of trees gives a natural way to process them, in the same way we've thought about functions on other recursive structures. First, let's consider the problem of counting how many nodes are in our tree. We can think of this as the size of the tree.
So as with all recursive algorithms, we want to think back to the definition of our structure. Well, what is a tree? It's either empty or a node. So we have two cases.
This gives us the following definition. The size of a tree $T$ is the number of nodes in $T$, denoted $\operatorname{size}(T)$, and is defined as follows:
As with the recursive functions we've seen, we can easily turn this definition into a function. Recall that we can override __len__ for this purpose.
def __len__(self):
"""
The number of nodes in the tree.
"""
if self.is_empty():
return 0
else:
sum = 1 # count the current node
for t in self.children:
sum = sum + t.__len__()
return sum
Just like the recursive functions we've seen before, we can "templatize" this.
def tree_function(tree):
if tree.is_empty():
# base case
else:
# recursive case
for t in tree.children:
# do something with tree_function(t), and key/value
Suppose now that we wanted to determine whether a key, say $k$, is present in our tree. Again, we consider how to solve this recursively. There are two possibilities for our tree: it's empty or it's not. If our tree is empty, then it obviously does not contain $k$.
But what if our tree is a node? One thing we can do is check whether the key in our node is $k$. If it is, then we can report that our tree does contain $k$. But what if it isn't? Well, it might be in one of the subtrees. So if it is in one of our subtrees, we can report this fact. Otherwise, we know the tree doesn't contain $k$.
Let's call this $\operatorname{contains}(T,k)$ and let's call the key stored in the node at $T$ (if it's a node) $\operatorname{key}(T)$. This is going to be a boolean: it's either true or false that $T$ contains $k$. We then have two possibilities.
This gives us the following code.
def __contains__(self, key):
if self.is_empty():
return False
else:
if key == self.key:
return True
else:
for t in self.children:
if t.__contains__(key):
return True
return False
This looks very similar to the definition we worked out and the other definitions we saw before. Again, it's helpful to keep the idea of using the recursive definition of the structure you're working on in mind when coming up with recursive programs.