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])