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

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)])
    """
    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_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]
    except (KeyError, IndexError):
        return missing

Use OK to test your code:

python3 ok -q quiet_get