If you need help reviewing Tree ADT, take a look at these resources:

Each question has a "Toggle Solution" button -- click it to reveal that question's solution.

Recall that we learned two different tree representations in this class:

• Abstract data type (defined in terms of functions). This is what this worksheet covers.
• Object-oriented programming (defined in termes of classes and methods). This will be covered in another review session.

The tree abstract data type is defined in terms of these four functions:

``````def tree(root, subtrees=[]):
return [root] + list(subtrees)

def root(t):
return t

def subtrees(t):
return t[1:]

def is_leaf(t):
return not subtrees(t)``````

Since this is an ADT, we don't care so much about the implementation of the constructors and selectors: as long as we know what they do, we can use them.

Remember, trees are recursively defined (trees are constructed using smaller trees). For most questions involving the tree ADT, you can break down the thought process into three steps:

1. Base case: Usually, this is if the tree is a leaf (use the `is_leaf` function)
2. Recursive call: Consider what a recursive call on a single branch will do. What information does it give you?
3. Recursive case: Make recursive calls on each branch (using a `for` loop or a list comprehension) and combine that in some way with the root for your final answer.

### Question 1

Implement a function `contains`, which takes a tree `t` and an element `e`. `contains` will return True if `t` contains the element `e`, and False otherwise.

``````def contains(t, e):
``````def contains(t, e):
if e == root(t):
return True
elif is_leaf(t):
return False
else:
for b in subtrees(t):
if contains(b, e):
return True
return False``````

It is possible to use a list comprehension to solve this problem, thanks to the built-in `any` function. The `any` function takes a list of booleans and returns True if any of those booleans is True:

``````def contains(t, e):
if e == root(t):
return True
elif is_leaf(t):
return False
else:
return any([contains(b, e) for b in subtrees(t)])``````

While this version is more concise, it is also more inefficient (why?).

### Question 2

Implement a function `all_paths`, which takes a tree `t`. `all_paths` will return a list of paths from the root to each leaf. For example, consider the following tree:

``````  5
/ \
3  6
/ \
2  1``````

Calling `all_paths` on this tree would return

``````[[5, 3, 2],
[5, 3, 1],
[5, 6]    ]``````

The list contains three paths (each path is itself a list).

``````def all_paths(t):
``````def all_paths(t):
if is_leaf(t):
return [[root(t)]]
else:
total = []
for b in subtrees(t):
for path in all_paths(b):
total.append([root(t)] + path)

It is possible to solve this using a list comprehension, but the list comprehension gets a little complicated:

``````def all_paths(t):
if is_leaf(t):
return [[root(t)]]
else:
return [[root(t)] + path for b in subtrees(t)
for path in all_paths(b)]``````

Notice that the `for` statements in the list comprehension are exactly the same as the two `for` loops in the original solution.

### Question 3

Implement a function `max_tree`, which takes a tree `t`. It returns a new tree with the exact same structure as `t`; at each node in the new tree, the entry is the largest number that is contained in that node's subtrees or the corresponding node in `t`. For example, consider this tree:

``````  5
/ \
3  6
/ \
2  4``````

Calling `max_tree` will return the following tree:

``````  6
/ \
4  6
/ \
2  4``````

For example, the largest number that occurs at the root or below it is 6 (i.e. `max(5, 3, 2, 4, 6) = 6`), so the root of the new tree is 6.

``````def max_tree(t):
``````def max_tree(t):