def tree(label, branches=[]):
    for b in branches:
        assert is_tree(b), 'branches must be trees'
    return [label] + list(branches)

def label(tree):
    return tree[0]

def branches(tree):
    return tree[1:]

def is_tree(tree):
    if type(tree) != list or len(tree) < 1:
        return False
    for b in branches(tree):
        if not is_tree(b):
            return False
    return True

def is_leaf(tree):
    return not branches(tree)

### +++ === ABSTRACTION BARRIER === +++ ###

def print_tree(t, indent=0):
    """ Prints levels of tree `t` indented by a space.
    >>> print_tree(tree(1))
    1
    >>> t = tree(3, [tree(1),
    ...              tree(2, [tree(1),
    ...                       tree(1)])])
    >>> print_tree(t)
    3
     1
     2
      1
      1
    """
    print(' ' * indent + str(label(t)))
    for b in branches(t):
        print_tree(b, indent + 1)

# First working solution
def count_nodes(t):
    """ Counts the number of nodes in tree `t`
    >>> count_nodes(tree(1))
    1
    >>> t = tree(8, [tree(4, [tree(2),
    ...                       tree(3)]),
    ...              tree(3, [tree(1),
    ...                       tree(1, [tree(1),
    ...                                tree(1)])])])
    >>> count_nodes(t)
    9
    """
    if is_leaf(t):
        return 1
    total = 1
    for b in branches(t):
        total += count_nodes(b)
    return total

# Taking out base case solution
def count_nodes(t):
    total = 1
    for b in branches(t):
        total += count_nodes(b)
    return total

# Simplified solution
def count_nodes(t):
    return 1 + sum([count_nodes(b) for b in branches(t)])

# First working solution
def list_leaves(t):
    """ Returns a list of the labels of the leaves from
    tree `t`.
    >>> list_leaves(tree(1))
    [1]
    >>> company_tree = tree('D', [tree('B', [tree('A'),
    ...                                      tree('C')]),
    ...                           tree('F', [tree('E'),
    ...                                      tree('H', [tree('G'),
    ...                                                 tree('I')])])])
    >>> list_leaves(company_tree)
    ['A', 'C', 'E', 'G', 'I']
    """
    if is_leaf(t):
        return [label(t)]
    leaves = []
    for b in branches(t):
        leaves += list_leaves(b)
    return leaves

# Simplified solution
def list_leaves(t):
    if is_leaf(t):
        return [label(t)]
    return sum([list_leaves(b) for b in branches(t)], [])

# First working solution
def square_tree(t):
    """ Returns a new tree with the same structure as `t`
    with every label squared.
    >>> print_tree(square_tree(tree(2)))
    4
    >>> t = tree(3, [tree(2),
    ...              tree(2, [tree(1),
    ...                       tree(1)])])
    >>> print_tree(square_tree(t))
    9
     4
     4
      1
      1
    """
    if is_leaf(t):
        return tree(label(t) ** 2)
    squared_branches = []
    for b in branches(t):
        squared_branches += [square_tree(b)]
    return tree(label(t) ** 2, squared_branches)

# Simplified solution
def square_tree(t):
    return tree(label(t) ** 2, [square_tree(b) for b in branches(t)])

def fib_tree(n):
    """ Returns a fib tree with root label fib(n) and its branches
    are also fib trees.
    >>> print_tree(fib_tree(0))
    0
    >>> print_tree(fib_tree(1))
    1
    >>> print_tree(fib_tree(4))
    3
     1
      0
      1
     2
      1
      1
       0
       1
    """
    if n == 0 or n == 1:
        return tree(n)
    left, right = fib_tree(n - 2), fib_tree(n - 1)
    fib_n = label(left) + label(right)
    return tree(fib_n, [left, right])