#
Lab 09: Trees

*Due at 11:59:59 pm on 11/7/2023.*

## Starter Files

Download lab09.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

## Efficiency

Recall that the order of growth of a function expresses how long it takes for the function to run, and is defined in terms of the function's input sizes.

For example, let's say that we have the function `get_x`

which is
defined as follows:

```
def get_x(x):
return x
```

`get_x`

has one expression in it. That one expression takes the same
amount of time to run, no matter what x is, or more importantly, how
large x gets. This is called constant time, or O(1).

The main two ways that a function in your program will get a running time different than just constant time is through either iteration or recursion. Let's start with some iteration examples!

The (simple) way you figure out the running time of a particular while loop is to simply count the cost of each operation in the body of the while loop, and then multiply that cost by the number of times that the loop runs. For example, look at the following method with a loop in it:

```
def foo(n):
i = 1
sum = 0
while i <= n:
sum = sum + i
i = i + 1
return sum
```

This loop has two statements in it `sum = sum + i`

and `i = i + 1.`

Each statement is a constant time operation, since the amount of time each statement takes does not depend on the input to the function `n`

.
In C88C, we are not concerned with how long primitive functions such as addition,
multiplication, and variable assignment take to run. Rather we are
concerned with *how many more times a loop is
executed* or *how many more recursive calls* occur as
the input increases. In this example, we execute the loop `n`

times, and
for each iteration, we only execute constant time operations, so we get
an order of growth of O(*n*).

Here are a couple of basic functions, along with their running times. Try to understand why they have the given running time.

O(n)

```
def bar(n):
i = 1
a = 1
b = 0
while i <= n:
temp = a
a = a + b
b = temp
i = i + 1
return a
```

O(n^2)

```
def bar(n):
sum = 0
a, b = 0, 0
while a < n:
while b < n:
sum += (a*b)
b += 1
b = 0
a += 1
return sum
```

**There is nothing to submit for this part.** But doing these problems will be good practice. The solutions are given right below the question and to see them you must highlight them.

### Question 1

What is the asymptotic run time of the baz function.

```
def baz(n):
i = 1
sum = 0
while i <= n:
sum += bam(i)
i += 1
return sum
def bam(n):
i = 1
sum = 0
while i <= n:
sum += i
i += 1
return sum
```

Highlight the text on the line below this line to see the solution:

Answer: O(*n*^{2})).

### Question 2

```
def bonk(n):
sum = 0
while n >= 2:
sum += n
n = n / 2
return sum
```

Highlight the text on the line below this line to see the solution:

Answer: O(log(*n*)).

## Trees

Our `Tree`

consists of an `value`

and a list of its
`branches`

. To create a tree and access its root and branches, use the
following constructor and selectors:

Constructor

`Tree(value, branches)`

: creates a tree object with the given`root`

and list of`branches`

.`Tree(value)`

: creates a tree object with no branches to make a leaf, similar to what we saw with linked lists.

Selectors

`tree.value`

: returns the value of the root of the`tree`

.`tree.branches`

: returns the list of branches of the given`tree`

.`tree.is_leaf()`

: returns`True`

if`tree`

's list of`branches`

is empty, and`False`

otherwise. Notice this is a function call

For example, 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 number `3`

from this tree, which is the value of the root of
its second branch, we would do this:

`t.branches[1].value`

Here is the implementation of the tree class, with the `__repr__`

function giving you what you need to type to create a tree when you enter an instance of the tree into the interpreter, and the `__str__`

function giving you a pretty version of a tree when you print it.

```
class Tree:
def __init__(self, value, branches=()):
self.value = value
for branch in branches:
assert isinstance(branch, Tree)
self.branches = list(branches)
def __repr__(self):
if self.branches:
branches_str = ', ' + repr(self.branches)
else:
branches_str = ''
return 'Tree({0}{1})'.format(self.value, branches_str)
def __str__(self):
def print_tree(t, indent=0):
tree_str = ' ' * indent + str(t.value) + "\n"
for b in t.branches:
tree_str += print_tree(b, indent + 1)
return tree_str
return print_tree(self).rstrip()
def is_leaf(self):
return not self.branches
```

### Question 3: Search

Write a function `search`

that returns the `Tree`

, whose root node is the given value if it exists and None if it does not. You can assume all values are unique.

```
def search(t, value):
"""Searches for and returns the Tree whose value is equal to value if
it exists and None if it does not. Assume unique values.
>>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
>>> search(t, 10)
>>> search(t, 5)
Tree(5)
>>> search(t, 1)
Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
>>> search(t, 7)
Tree(7)
"""
"*** YOUR CODE HERE ***"
if t.value == value:
return t
for branch in t.branches:
result = search(branch, value)
if result is not None:
return result
return
```

Use OK to test your code:

`python3 ok -q search`

### Question 4: Cumulative Sum

Write a function `cumulative_sum`

that returns a new `Tree`

, where each value is the sum of all values in the corresponding subtree of the old `Tree`

.

```
def cumulative_sum(t):
"""Return a new Tree, where each value is the sum of all values in the
corresponding subtree of t.
>>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
>>> cumulative = cumulative_sum(t)
>>> t
Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
>>> cumulative
Tree(16, [Tree(8, [Tree(5)]), Tree(7)])
>>> cumulative_sum(Tree(1))
Tree(1)
"""
"*** YOUR CODE HERE ***"
subtrees = [cumulative_sum(st) for st in t.branches]
new_value = sum(st.value for st in subtrees) + t.value
return Tree(new_value, subtrees)
```

Use OK to test your code:

`python3 ok -q cumulative_sum`

### Question 5: Add Leaves

Implement `add_d_leaves`

, a function that takes in a `Tree`

instance `t`

and
mutates it so that at each depth `d`

in the tree, `d`

leaves with labels `v`

are added to each node at that depth. For example, we want to add 1 leaf with
`v`

in it to each node at depth 1, 2 leaves to each node at depth 2, and so on.

Recall that the depth of a node is the number of edges from that node to the root, so the depth of the root is 0. The leaves should be added to the end of the list of branches.

```
def add_d_leaves(t, v):
"""Add d leaves containing v to each node at every depth d.
>>> t1 = Tree(1, [Tree(3)])
>>> add_d_leaves(t1, 4)
>>> t1
Tree(1, [Tree(3, [Tree(4)])])
>>> t2 = Tree(2, [Tree(5), Tree(6)])
>>> t3 = Tree(3, [t1, Tree(0), t2])
>>> add_d_leaves(t3, 10)
>>> print(t3)
3
1
3
4
10
10
10
10
10
10
0
10
2
5
10
10
6
10
10
10
"""
def add_leaves(t, d):
"*** YOUR CODE HERE ***"
for b in t.branches:
add_leaves(b, d + 1)
t.branches.extend([Tree(v) for _ in range(d)]) add_leaves(t, 0)
```

Use OK to test your code:

`python3 ok -q add_d_leaves`

## Exceptions

Exceptions allow us to try a chunk of code, and then catch any errors that might come up. If we do catch an exception, we can run an alternative set of instructions. This construct is very useful in many situations.

```
try:
<try suite>
except Exception as e:
<except suite>
else:
<else suite>
finally:
<finally suite>
```

Notice that we can catch the exception as `e`

. This binds the name `e`

to
the exception object. This can be helpful when we want to give extra
information on what happened. For example, we can `print(e)`

inside the
except clause.

Also, we have an optional else case. The else suite is executed if the
`try`

suite finishes without any exceptions.

We also have an optional finally clause, which is always executed, whether or not an exception is thrown. We generally don't need to use the else and finally controls in this class.

When we write exception statements, we generally don't just use the
class Exception as above. Rather, we figure out the specific type of
exception that we want to handle, such as `TypeError`

or
`ZeroDivisionError`

. To figure out which type of exception you are trying
to handle, you can type purposely wrong things into the interpreter
(such as 'hi' + 5 or 1 / 0) and see what kind of exception Python spits
out.

### Question 6: No KeyErrors Allowed

If we try to look up a key that does not exist in a dictionary, then
Python will raise a `KeyError`

. Write the function `avoid_keyerror`

which
returns the value mapped to `key`

in the `dictionary`

. If `key`

does
not exist, print 'Avoid Exception' and set `key`

to the string 'no value'.

```
def avoid_keyerror(dictionary, key):
""" Returns the value associated with key in dictionary. If key
does not exist in the dictionary, print out 'Avoid Exception' and
map it to the string 'no value'.
>>> d = {1: 'one', 3: 'three', 5: 'five'}
>>> avoid_keyerror(d, 3)
'three'
>>> avoid_keyerror(d, 4)
Avoid Exception
>>> d[4]
'no value'
"""
"*** YOUR CODE HERE ***"
try:
return dictionary[key]
except KeyError as e:
print("Avoid Exception")
dictionary[key] = 'no value'
```

Use OK to test your code:

`python3 ok -q avoid_keyerror`

## Submission

When you are done, submit your file to Gradescope. You only need to upload the following files:

`lab09.py`