## Instructions

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

Readings: This homework relies on following references:

## 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 1: Same Shape

Write a function `same_shape` that returns `True` if two `Tree`s have the same shape. Two trees have the same shape if they have the same number of children and each of their children have the same shape.

``````def same_shape(t1, t2):
"""Returns whether two Trees t1, t2 have the same shape. Two trees have the
same shape if they have the same number of branches and each of their
children have the same shape.

>>> t, s = Tree(1), Tree(3)
>>> same_shape(t, t)
True
>>> same_shape(t, s)
True
>>> t = Tree(1, [Tree(2), Tree(3)])
>>> same_shape(t, s)
False
>>> s = Tree(4, [Tree(7)])
>>> same_shape(t, s)
False
>>> s.branches.append(Tree(6)) # Add a new leaf to s to make it same shape as t
>>> same_shape(t, s)
True
>>> t1 = Tree(1, [Tree(2, [Tree(3), Tree(4)]), Tree(5)])
>>> t2 = Tree(6, [Tree(7), Tree(8, [Tree(9), Tree(10)])])
>>> same_shape(t1, t2)
False
>>> t1 = Tree(1, [Tree(2, [Tree(4), Tree(5)]), Tree(3)])
>>> t2 = Tree(9, [Tree(8, [Tree(6), Tree(7)]), Tree(10)])
>>> same_shape(t1, t2)
True
>>> t1 = Tree(1, [Tree(2, [Tree(4, [Tree(6)])]), Tree(3)])
>>> t2 = Tree(9, [Tree(8, [Tree(7, [Tree(5)])]), Tree(10)])
>>> same_shape(t1, t2)
True
"""

Use OK to test your code:

``python3 ok -q same_shape``

### Question 2: 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)
"""

Use OK to test your code:

``python3 ok -q cumulative_sum``

### Question 3: Find Level

Implement `find_level`, which takes a tree `t` and an integer `level` and returns a list of all the values that have depth `level`. If no such values exist, return the empty list. For a refresher on the depth of a node, check out here.

``````def find_level(t, level):
"""
>>> t = Tree(1, [Tree(2, [Tree(4), Tree(5)]), Tree(6, [Tree(7)])])
>>> find_level(t, 2)
[4, 5, 7]
>>> find_level(t, 1)
[2, 6]
>>> find_level(t, 5)
[]
"""

Use OK to test your code:

``python3 ok -q find_level``

### Question 4: Merge Trees

Implement `merge_trees`, which takes in two trees `t1` and `t2` and merges them into a single new tree where each entry is the result of applying the two-argument function `fn` to each of the corresponding entries. Assume `t1` and `t2` are the same shape, so the merge is always possible.

``````def merge_trees(t1, t2, fn):
"""
>>> one = Tree(1, [Tree(2, [Tree(4), Tree(5)]), Tree(6)])
>>> two = Tree(11, [Tree(10, [Tree(10), Tree(10)]), Tree(10)])
>>> merge_trees(one, two, lambda x, y: x + y)
Tree(12, [Tree(12, [Tree(14), Tree(15)]), Tree(16)])
>>> merge_trees(one, two, lambda x, y: y - x)
Tree(10, [Tree(8, [Tree(6), Tree(5)]), Tree(4)])
"""

Use OK to test your code:

``python3 ok -q merge_trees``

## Exceptions

You've learned how to raise exceptions, but it's also important to catch exceptions when necessary. Instead of letting the exception propogate back to the user, we can catch it using a `try...except` block and allow the program to continue.

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

We put the code that might raise an exception in the `<try suite>`. If an exception of type `Exception` is raised, then the program will skip the rest of that suite and execute the `<except suite>`. Generally, we want to be specify exactly which `Exception` we want to handle, such as `TypeError` or `ZeroDivisionError`.

Notice that we can catch the exception `as e`. This assigns the exception object to the variable `e`. This can be helpful when we want to use information about the exception that was raised.

``````>>> try:
...     1/0
...     raise ValueError     # this line is not executed!
... except ZeroDivisionError as e:
...     print('The try block raised a ' + str(e) + ' error.')
The try block raised a division by zero error.``````

### Question 5: Quiet get

You have seen that indexing into a list with an invalid index raises an exception. For example:

``````>>> lst = [5, 4, 3]
>>> lst[5]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError: list index out of range``````

Similarly, looking up a key that doesn't exist in a dictionary raises an exception.

``````>>> dct = {'a': 1}
>>> dct['b']
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
KeyError: 'b'``````

However, the `get` method of `dict` is more forgiving. If the key is not in the dictionary it returns a value that you provide, defaulting to `None`. For example:

``````>>> retrieved = dct.get('b')
>>> print(retrieved)
None
>>> dct.get('b', 'wow')
'wow'``````

Use exception handling to complete the function `quiet_get` to obtain similar behavior for both lists and dictionaries.

We have provided the `try` part of the statement using indexing, rather than `get`. You need to write the `except` clause.

``````def quiet_get(data, selector, missing=None):
"""Return data[selector] if it exists, otherwise return missing.

>>> quiet_get([1, 2, 3], 1)
2
>>> quiet_get([1, 2, 3], 4) # no missing argument passed in, so returns None
>>> quiet_get([1, 2, 3], 4, -1)
-1
>>> quiet_get({'a': 2, 'b': 5}, 'a', -1)
2
>>> quiet_get({'a': 2, 'b': 5}, 'd', -1)
-1
"""
try:
return data[selector]
``python3 ok -q quiet_get``
• `hw09.py`