# Lab 05: Orders of Growth and Hierarchical Data Structures

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

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.

### Implementation

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

### Question 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
"""
``````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``````

### Question 2

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]
"""
``````from functools import reduce

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``````

### Question 3

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
"""
``````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)``````

## Midterm 1 Review Questions

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

1. They are meant for you to get more practice.

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

## Environment Diagrams

Draw the environment diagrams for the following questions.

### Question 4

``````def funny(joke):
hoax = joke + 1
return funny(hoax)

hoax = joke - 1
return hoax + hoax

### Question 5

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

### Question 6

``````def easy(x):
def peasy(y):
def ironic(name):
return name(x, y)
return y
return peasy

result = easy(4)(easy)(2)``````

## Data Abstraction

### Question 7

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

### Question 8

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.

< 1 2 >
>>> lst2 = insert_at_end(lst1, 3)
< 1 2 3 >
"""
``````def insert_at_end(lst, elem):
if lst == empty:
else:

### Question 9

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.

< 1 2 3 >
>>> reversed_lst = reverse(lst)
< 3 2 1 >
"""
``````def reverse(lst):
if lst == empty:
return empty
else:
return insert_at_end(reverse(rest(lst)), first(lst))``````

## Functions

### Question 10

Determine the result of the following expression.

``````from operator import add, sub, mul, truediv

### Question 11

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()))``````

### Question 12

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``````