# Lab 9 Solutions

## Trees

Our `Tree`

consists of an `entry`

and a list of its
`branches`

. To create a tree and access its root and branches, use the
following constructor and selectors:

Constructor

`Tree(entry, 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.entry`

: returns the value of the entry 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].entry`

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, entry, branches=()):
self.entry = entry
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.entry, branches_str)
def __str__(self):
def print_tree(t, indent=0):
tree_str = ' ' * indent + str(t.entry) + "\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
```

Below is an example of a type of tree problem you could encounter. We are trying to apply a function onto each value of a tree. There are many steps that are involved in stepping through all the code, but it is most important to understand each part of the function. There are annotations that break down the solution to this problem.

### Question 1: WWPP: Trees

Use OK to test your knowledge with the following "What Would Python Print?" questions:

`python3 ok -q trees -u`

Hint: Remember for all WWPP questions, enter`Function`

if you believe the answer is`<function ...>`

and`Error`

if it errors.

```
>>> from lab09 import *
>>> t = Tree(1, Tree(2))
______Error
>>> t = Tree(1, [Tree(2)])
>>> t.entry
______1
>>> t.branches[0]
______Tree(2)
>>> t.branches[0].entry
______2
>>> t.entry = t.branches[0].entry
>>> t
______Tree(2, [Tree(2)])
>>> t.branches.append(Tree(4, [Tree(8)]))
>>> len(t.branches)
______2
>>> t.branches[0]
______Tree(2)
>>> t.branches[1]
______Tree(4, [Tree(8)])
```

### 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)])
"""
"*** YOUR CODE HERE ***"
t.entry = t.entry ** 2
for subtree in t.branches:
square_tree(subtree)
```

Use OK to test your code:

`python3 ok -q square_tree`

### Question 3: 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]
"""
"*** YOUR CODE HERE ***"
if t.is_leaf():
return [t.entry]
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 4: Same Shape

Write a function `same_shape`

that returns `True`

if two `Tree`

s 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 ***"
return len(t1.branches) == len(t2.branches) and \
all([same_shape(st1, st2) for st1, st2 in zip(t1.branches, t2.branches)])
```

Use OK to test your code:

`python3 ok -q same_shape`

### Question 5: Cumulative Sum

Write a function `cumulative_sum`

that returns a new `Tree`

, where each entry is the sum of all entries in the corresponding subtree of the old `Tree`

.

```
def cumulative_sum(t):
"""Return a new Tree, where each entry is the sum of all entries 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_entry = sum(st.entry for st in subtrees) + t.entry
return Tree(new_entry, subtrees)
```

Use OK to test your code:

`python3 ok -q cumulative_sum`

## Submit

Make sure to submit this assignment by running:

`python3 ok --submit`

# Extra Credit Practice Open in a new window

These questions are new this semester. They're a mix of Parsons Problems, Code Tracing questions, and Code Writing questions.

Confused about how to use the tool? Check out https://codestyle.herokuapp.com/cs88-lab01 for some problems designed to demonstrate how to solve these types of problems.

These cover some similar material to lab, so can be helpful to further review or try to learn the material. Unlike lab and homework, after you've worked for long enough and tested your code enough times on any of these questions, you'll have the option to view an instructor solution. You'll unlock each question one at a time, either by correctly answering the previous question or by viewing an instructor solution.

**Starting from lab 2 onward, each set of questions are worth half (0.5) a point per lab, for a total opportunity of 4-5 points throughout the semester.**

Use OK to test your code:

`python3 ok -q extra_credit`