Definition

Recursive definition: A tree is either:

empty, or
has a root value connected to any number of other trees

> A tree can contain a root value but not have any subtrees

Some more definitions...

The size of a tree is the number of values in the tree.
A leaf is a value with no subtrees
The opposite of a leaf is an internal value
The height of a tree is the length of the longest path from its root to one of its leaves
The children of a value are all values directly connected underneath that value
The descendants of a value are its children, the children of its children, etc.
- recursively: the descendants are its children, and the descendants of its children
The parent of a value is the value immediately above it and connected to it.
The ancestors of a value are its parent, the parent of its parent, etc,
- recursively: the ancestors are its parent, and the ancestors of its parent

Implementation

from future import annotations from typing import Any, Optional

class Tree:
    """A recursive tree data structure.

    Representation Invariants:
        - self._root is not None or self._subtrees == []
    """
    # Private Instance Attributes:
    #   - _root:
    #       The item stored at this tree's root, or None if the tree is empty.
    #   - _subtrees:
    #       The list of subtrees of this tree. This attribute is empty when
    #       self._root is None (representing an empty tree). However, this attribute
    #       may be empty when self._root is not None, which represents a tree consisting
    #       of just one item.
    _root: Optional[Any]
    _subtrees: list[Tree]

    def __init__(self, root: Optional[Any], subtrees: list[Tree]) -> None:
        """Initialize a new Tree with the given root value and subtrees.

        If root is None, the tree is empty.

        Preconditions:
            - root is not none or subtrees == []
        """
        self._root = root
        self._subtrees = subtrees

    def is_empty(self) -> bool:
        """Return whether this tree is empty.
        """
        return self._root is None