Tree Recursion Template

class Tree:
    def method(self) -> ...:
        if self.is_empty():         # tree is empty
            ...
        elif self._subtrees == []:  # tree is a single value
            ...
        else:                       # tree has at least one subtree
            ...
            for subtree in self._subtrees:
                ... subtree.method() ...
            ...

Calculating the Size of a Tree

Let $T$ be a tree, and let $size$ be a function mapping a tree to its size.

• If $T$ is empty, then $size(T) = 0$
• If $T$ is non-empty, then it consists of a root value and a collection of subtrees $T_{0},T_{1},\dots,T_{k-1}$ (for some $k \in \mathbb{N}$). In this case: $$ size(T) = 1 + \sum_{i=0}^{k-1}size(T_{i}) $$ Formally: $$ size(T) = \begin{cases} 0, & \text{if } T \text{ is empty} \\ 1 + \sum_{i=0}^{k-1} size(T_{i}), & \text{ if} T \text{ has subtrees } T_{0},T_{1},\dots,T_{k-1} \end{cases} $$

Implementation

class Tree:
    def __len__(self) -> int:
        """Return the number of items contained in this tree.

        >>> t1 = Tree(None, [])
        >>> len(t1)
        0
        >>> t2 = Tree(3, [Tree(4, []), Tree(1, [])])
        >>> len(t2)
        3
        """
        if self.is_empty():
            return 0
        else:
		return 1 + sum(subtree.__len__() for subtree in self._subtrees)

or more explicitly:

class Tree:
    def __len__(self):
        if self.is_empty():         # tree is empty
            return 0
        elif self._subtrees == []:  # tree is a single item
            return 1
        else:                       # tree has at least one subtree
            return 1 + sum(subtree.__len__() for subtree in self._subtrees)

Displaying a Tree (__str__)