#
Lab 09: Trees

*Due at 11:59:59 pm on 4/18/2023.*

## Starter Files

Download lab09.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

## Submission

By the end of this lab, you should have submitted the lab with `python3 ok --submit`

. You may submit more than once before the deadline; only the final submission will be graded. Check that you have successfully submitted your code on okpy.org.

## Trees

### Question 1: Search

Write a function `search`

that returns the `Tree`

, whose root node is the given value if it exists and None if it does not. You can assume all values are unique.

```
def search(t, value):
"""Searches for and returns the Tree whose value is equal to value if
it exists and None if it does not. Assume unique values.
>>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
>>> search(t, 10)
>>> search(t, 5)
Tree(5)
>>> search(t, 1)
Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
>>> search(t, 7)
Tree(7)
"""
"*** YOUR CODE HERE ***"
if t.value == value:
return t
for branch in t.branches:
result = search(branch, value)
if result is not None:
return result
return
```

Use OK to test your code:

`python3 ok -q search`

### 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)
"""
"*** YOUR CODE HERE ***"
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: Add Leaves

Implement `add_d_leaves`

, a function that takes in a `Tree`

instance `t`

and
mutates it so that at each depth `d`

in the tree, `d`

leaves with labels `v`

are added to each node at that depth. For example, we want to add 1 leaf with
`v`

in it to each node at depth 1, 2 leaves to each node at depth 2, and so on.

Recall that the depth of a node is the number of edges from that node to the root, so the depth of the root is 0. The leaves should be added to the end of the list of branches.

```
def add_d_leaves(t, v):
"""Add d leaves containing v to each node at every depth d.
>>> t1 = Tree(1, [Tree(3)])
>>> add_d_leaves(t1, 4)
>>> t1
Tree(1, [Tree(3, [Tree(4)])])
>>> t2 = Tree(2, [Tree(5), Tree(6)])
>>> t3 = Tree(3, [t1, Tree(0), t2])
>>> add_d_leaves(t3, 10)
>>> print(t3)
3
1
3
4
10
10
10
10
10
10
0
10
2
5
10
10
6
10
10
10
"""
def add_leaves(t, d):
"*** YOUR CODE HERE ***"
for b in t.branches:
add_leaves(b, d + 1)
t.branches.extend([Tree(v) for _ in range(d)]) add_leaves(t, 0)
```

Use OK to test your code:

`python3 ok -q add_d_leaves`

## Submit

Make sure to submit this assignment by running:

`python3 ok --submit`