By the end of this lab, you should have submitted the
`lab05`

assignment using the command `submit lab05`

.

**This lab is due by 11:59pm on 7/10/2014.**

Here is a lab05.py starter file for this lab.

Trees are a way we have of representing a hierarchy of information. A file directory is a good example of something with a tree structure. You have a root folder that contains several other folders — home, bin, user, etc. — and within each of these there exists a similar hierarchy.

The name "tree" comes from the branching structure, like real trees in nature except that they're drawn with the root at the top and the leaves at the bottom.

**Terminology**:

**node**: a point in the tree. In these pictures, each node includes a datum (value at each node)**root**: the node at the top. Every tree has one root node**children**: the children of a node are the nodes directly beneath the node.**arity**: the number of children that a node has.**leaf**: a node that has no children. (Arity of 0)**depth**: the depth of a node is the number of levels below the root node of the tree. The depth of the root is 0, and the depth of its children is 1.

For this lab, we will be using trees according to the following specification unless otherwise stated.

A tree consists of a `datum`

and a list of children. Each of these children is itself a tree. A leaf is represented as a tree whose list of children is an empty list.

Our implementation of trees can be found in `lab05.py`

, though since it is an ADT, the implementation is not important. The interface for our trees consists of the following functions:

```
# Constructor
tree(datum, children=[])
# Selectors
datum(tree)
children(tree)
```

Therefore the tree generated by

```
t = tree(1, [tree(2),
tree(3, [tree(4), tree(5)]),
tree(6, [tree(7)])])
```

would look like this:

```
1
/ | \
2 3 6
/ \ \
4 5 7
```

It may be easier to visualize this translation by formatting the code like this:

```
t = tree(1,
[tree(2),
tree(3,
[tree(4),
tree(5)]),
tree(6,
[tree(7)])])
```

To extract the `3`

from this tree, we would do this:

`datum(children(t)[1])`

Define the function `size_of_tree`

, which takes in a tree as an argument and returns the number of entries in the tree.

```
def size_of_tree(t):
"""Return the number of entries in the tree.
>>> print_tree(t)
1
2
3
4
5
6
7
>>> size_of_tree(t)
7
"""
"*** YOUR CODE HERE ***"
```

```
def size_of_tree(t):
return 1 + sum([size_of_tree(t) for t in children(t)])
```

OR

```
def size_of_tree(t):
children_sum = 0
for child in children(t):
children_sum += size_of_tree(child)
return 1 + children_sum
```

Define the function `flatten`

, which takes in a tree as an argument and returns a list of all the entries in the tree in the order that `print_tree`

would print them. This ordering of the nodes in a tree is called a preorder traversal (you will learn about more orders of traversing a tree in CS 61B).

```
def flatten(t):
"""Return a list of the entries in this tree in the order that they
would be visited by a preorder traversal (see problem description).
>>> flatten(t)
[1, 2, 3, 4, 5, 6, 7]
>>> flatten(tree(2, [tree(4, [tree(6)])]))
[2, 4, 6]
"""
"*** YOUR CODE HERE ***"
```

```
from functools import reduce
from operator import add
def flatten(t):
return reduce(add, [flatten(child) for child in children(t)], [datum(t)])
```

OR

```
def flatten(t):
if children(t) == []:
return [datum(t)]
flattened_children = []
for child in children(t):
flattened_children += flatten(child)
return [datum(t)] + flattened_children
```

Define the function `tree_map`

, which takes in a tree and a one-argument function as arguments and returns a new tree which is the result of mapping the function over the entries of the input tree.

```
def tree_map(fn, t):
"""Maps the function fn over the entries of tree and returns the
result in a new tree.
>>> print_tree(tree_map(lambda x: 2**x, t))
2
4
8
16
32
64
128
"""
"*** YOUR CODE HERE ***"
```

```
def tree_map(fn, t):
return tree(fn(datum(t)), [tree_map(fn, t) for t in children(t)])
```

OR

```
def tree_map(fn, t):
if children(t) == []:
return tree(fn(datum(t)), [])
mapped_children = []
for child in children(t):
mapped_children += [ tree_map(fn, child) ]
return tree(fn(datum(t)), mapped_children)
```

The rest of the questions on this lab will **not be turned in** for Lab

- They are meant for you to get more practice.

Here is a review1.py starter file for this section.

Draw the environment diagrams for the following questions.

```
def funny(joke):
hoax = joke + 1
return funny(hoax)
def sad(joke):
hoax = joke - 1
return hoax + hoax
funny, sad = sad, funny
result = funny(sad(1))
```

```
def fun(fun):
def time(time):
return fun(x)
x = 4
return time
def boo(x):
return x**2
x = 5
result = fun(boo)(10)
```

```
def easy(x):
def peasy(y):
def ironic(name):
return name(x, y)
return y
return peasy
result = easy(4)(easy)(2)
```

Suppose that your friend wrote the following function `prod_rats`

that
takes a list of rational numbers using our ADT and returns their
product. Correct their code so that they do not have any data
abstraction violations.

```
def prod_rats(rats):
"""Returns a rational number that is the product of the rational
numbers in rats.
>>> x = prod_rats([make_rat(2, 4), make_rat(5, 9), make_rat(6, 4)])
>>> num(x)
5
>>> den(x)
12
"""
total, i = [1, 1], 0
while i < len(rats):
total = [total[0]*rats[i][0], total[1]*rats[i][1]]
i += 1
g = gcd(total[0], total[1])
return [total[0] // g, total[1] // g]
```

```
def prod_rats(rats):
total, i = make_rat(1, 1), 0
while i < len(rats):
total = mul_rat(total, rats[i])
i += 1
return total
```

Write a function that returns a new linked list that is the same as
`lst`

with `elem`

added at the end.

```
def insert_at_end(lst, elem):
"""Return a linked list that is the same as lst with elem added
at the end.
>>> lst1 = link(1, link(2, empty))
>>> print_linked_list(lst1)
< 1 2 >
>>> lst2 = insert_at_end(lst1, 3)
>>> print_linked_list(lst2)
< 1 2 3 >
"""
"*** YOUR CODE HERE ***""
```

```
def insert_at_end(lst, elem):
if lst == empty:
return link(elem, empty)
else:
return link(first(lst), insert_at_end(rest(lst), elem))
```

Write a function that uses the previous `insert_at_end`

function and
returns a new list that contains the elements of `lst`

in reverse
order.

```
def reverse(lst):
"""Returns a new list that contains the elements of lst in reverse order.
>>> lst = link(1, link(2, link(3, empty)))
>>> print_linked_list(lst)
< 1 2 3 >
>>> reversed_lst = reverse(lst)
>>> print_linked_list(reversed_lst)
< 3 2 1 >
"""
"*** YOUR CODE HERE ***"
```

```
def reverse(lst):
if lst == empty:
return empty
else:
return insert_at_end(reverse(rest(lst)), first(lst))
```

Determine the result of the following expression.

```
from operator import add, sub, mul, truediv
truediv(mul(add(5, 3), sub(4, 2)), 4)
```

What would Python print?

```
from operator import mul
def hi():
print(“yummy”)
return mul
def welcome():
print("chicken")
return max
def to():
print("dinner")
return 5
def cs61a():
print("winner")
return 10
hi()(welcome()(to(), cs61a()), welcome()(cs61a(), to()))
```

Fill in the blanks so that the doctests pass!

```
def catchphrase(say, person):
"""
>>> say = lambda a: 'Darknesss' if a == 'Nocturne' else 'Mundo'
>>> phrase = catchphrase(say, None)
Welcome to Summoner's Rift!
>>> phrase
False
>>> catchphrase(say, 'Mundo')
'Mundo'
>>> catchphrase(say, 'Nocturne')
'report feeder'
"""
if ______:
print("Welcome to Summoner's Rift!")
return ______
if say(person) == 'Darknesss':
return 'report feeder'
else:
_____
```

```
def catchphrase(say, person):
if person == None:
print("Welcome to Summoner's Rift!")
return False
if say(person) == 'Darknesss':
return 'report feeder'
else:
return person
```