Homework 10 Solutions

**Solutions:** You can find the file with solutions for all
questions here.

## Trees

### Question 1: Leaves

Write a function `leaves`

that returns a list of all the entries 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))
[1]
>>> leaves(Tree(1, [Tree(2, [Tree(3)]), Tree(4)]))
[3, 4]
"""
if t.is_leaf():
return [t.value]
all_leaves = []
for b in t.branches:
all_leaves += leaves(b)
return all_leaves
```

Use OK to test your code:

`python3 ok -q leaves`

### Question 2: Path

Write a function `path`

that returns the path from the root of the tree to the given entry value if it exists and [] if it does not. You can assume all entries are unique.

```
def path(t, value):
"""
>>> 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)
[]
"""
if t.value == value:
return [value]
elif t.is_leaf():
return []
else:
for b in t.branches:
rest = path(b, value)
if rest:
return [t.value] + rest
return []
```

Use OK to test your code:

`python3 ok -q path`

### Question 3: Find Level

Implement `find_level`

, which takes a tree `t`

and an integer `level`

and returns a list of all the entries that have depth `level`

. If no such entries exists, 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`

## Submit

Make sure to submit this assignment by running:

`python3 ok --submit`