Homework 9 Solutions
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 givenrootand list ofbranches.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 thetree.tree.branches: returns the list of branches of the giventree.tree.is_leaf(): returnsTrueiftree's list ofbranchesis empty, andFalseotherwise. 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 7It 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].valueHere 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.branchesQuestion 1: Same Shape
Write a function same_shape that returns True if two Trees 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
"""
if len(t1.branches) != len(t2.branches):
return False
for i in range(len(t1.branches)):
if not same_shape(t1.branches[i], t2.branches[i]):
return False
return TrueUse OK to test your code:
python3 ok -q same_shapeQuestion 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)
"""
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_sumQuestion 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)
[]
"""
if level == 0:
return [t.value]
elif t.is_leaf():
return []
else:
lst = []
for b in t.branches:
lst += find_level(b, level - 1)
return lstUse OK to test your code:
python3 ok -q find_levelQuestion 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)])
"""
if t1.is_leaf():
return Tree(fn(t1.value, t2.value))
else:
branches = []
for b1, b2 in zip(t1.branches, t2.branches):
branches.append(merge_trees(b1, b2, fn))
return Tree(fn(t1.value, t2.value), branches)Use OK to test your code:
python3 ok -q merge_treesExceptions
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 rangeSimilarly, 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]
except (KeyError, IndexError):
return missingUse OK to test your code:
python3 ok -q quiet_get