Homework 9
Due at 11:59:59 pm on Thursday, 11/09/2023.

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:

• Section 2.9.1

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 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
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q same_shape

Question 2: 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)
    []
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q find_level

Question 3: 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)])
    """
    "*** YOUR CODE HERE ***"

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 4: Quiet get

You have seen that indexing a list with an index that is not contained in the list generates and exception, as does looking up a key that does not exist in a dictionary. 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. Use exception handling in the function quiet_get to obtain similar behavior for both lists and dictionaries.

We have provide 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]
"*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q quiet_get

Submission

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

• hw09.py