## 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.

Submission: When you are done, submit with `python3 ok --submit`. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on okpy.org.

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`. You can also call it with no branches to make a leaf, just like we saw with links.
• 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.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: Leaves

Write a function `leaves` that returns a list of all the values of the leaf nodes of a `Tree`.

``````def leaves(t):
"""Returns a list of all the entries of the leaf nodes of the Tree t.

>>> leaves(Tree(1))

>>> leaves(Tree(1, [Tree(2, [Tree(3)]), Tree(4)]))
[3, 4]
"""

Use OK to test your code:

``python3 ok -q leaves``

### Question 2: Square Tree

Write a function `square_tree` that mutates a `Tree` with numerical entries so that each entry is squared.

``````def square_tree(t):
"""Mutates a Tree t by squaring all its elements.

>>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
>>> square_tree(t)
>>> t
Tree(1, [Tree(9, [Tree(25)]), Tree(49)])
"""

Use OK to test your code:

``python3 ok -q square_tree``

### Question 3: Path

Write a function `path` that returns the path from the root of the tree to the given value `target` as a list if it exists and `[]` if it does not. You can assume all values are unique.

``````def path(t, target):
"""
>>> t = Tree(9, [Tree(7, [Tree(3), Tree(2)]), Tree(5)])
>>> path(t, 2)
[9, 7, 2]
>>> path(t, 5)
[9, 5]
>>> path(t, 8)
[]
"""

Use OK to test your code:

``python3 ok -q path``

### Question 4: 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)
[]
"""
``python3 ok -q find_level``
``python3 ok --submit``