# Lab 9: Mutable Trees, Efficiency

*Due by 11:59pm on Wednesday, March 22.*

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

# Topics

Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.

## Mutable Trees

We define a tree to be a recursive data abstraction that has a `label`

(the
value stored in the root of the tree) and `branches`

(a list of trees directly
underneath the root).

Previously we implemented trees by using a functional data abstraction, with the `tree`

constructor function and the `label`

and `branches`

selector functions. Now we implement trees by creating the `Tree`

class. Here is part of the class included in the lab.

```
class Tree:
"""
>>> t = Tree(3, [Tree(2, [Tree(5)]), Tree(4)])
>>> t.label
3
>>> t.branches[0].label
2
>>> t.branches[1].is_leaf()
True
"""
def __init__(self, label, branches=[]):
for b in branches:
assert isinstance(b, Tree)
self.label = label
self.branches = list(branches)
def is_leaf(self):
return not self.branches
```

Even though this is a new implementation, everything we know about the functional tree data abstraction
remains true. That means that solving problems involving trees as objects uses
the same techniques that we developed when first studying the functional tree data abstraction (e.g. we
can still use recursion on the branches!). **The main difference, aside from syntax, is that tree objects are mutable.**

Here is a summary of the differences between the tree data abstraction implemented as a functional abstraction vs. implemented as class:

- | Tree constructor and selector functions | Tree class |
---|---|---|

Constructing a tree | To construct a tree given a `label` and a list of `branches` , we call `tree(label, branches)` |
To construct a tree object given a `label` and a list of `branches` , we call `Tree(label, branches)` (which calls the `Tree.__init__` method). |

Label and branches | To get the label or branches of a tree `t` , we call `label(t)` or `branches(t)` respectively |
To get the label or branches of a tree `t` , we access the instance attributes `t.label` or `t.branches` respectively. |

Mutability | The functional tree data abstraction is immutable because we cannot assign values to call expressions | The `label` and `branches` attributes of a `Tree` instance can be reassigned, mutating the tree. |

Checking if a tree is a leaf | To check whether a tree `t` is a leaf, we call the convenience function `is_leaf(t)` |
To check whether a tree `t` is a leaf, we call the bound method `t.is_leaf()` . This method can only be called on `Tree` objects. |

## Efficiency (Orders of Growth)

**tricky examples are 61B topics, not 61A topics**. In addition to classifying algorithms as Exponential, Quadratic, Linear, Logarithmic, or Constant, we also introduce Big Theta notation, but do not go into the details of runtime analysis.

When we talk about the efficiency of a function, we are often interested in the
following: as the size of the input grows, how does the runtime of the function
change? And what do we mean by *runtime*?

**Example 1:** `square(1)`

requires one primitive operation: multiplication.
`square(100)`

also requires one. No matter what input `n`

we pass into `square`

, it always takes a *constant* number of operations (1). In other words, this function has a runtime complexity of Θ(1).

As an illustration, check out the table below:

input | function call | return value | operations |
---|---|---|---|

1 | `square(1)` |
1*1 | 1 |

2 | `square(2)` |
2*2 | 1 |

... | ... | ... | ... |

100 | `square(100)` |
100*100 | 1 |

... | ... | ... | ... |

n | `square(n)` |
n*n | 1 |

**Example 2:** `factorial(1)`

requires one multiplication, but `factorial(100)`

requires 100 multiplications. As we increase the input size of n, the runtime (number of operations) increases **linearly** proportional to the input. In other words, this function has a runtime complexity of Θ(`n`

).

As an illustration, check out the table below:

input | function call | return value | operations |
---|---|---|---|

1 | `factorial(1)` |
1*1 | 1 |

2 | `factorial(2)` |
2*1*1 | 2 |

... | ... | ... | ... |

100 | `factorial(100)` |
100*99*...*1*1 | 100 |

... | ... | ... | ... |

n | `factorial(n)` |
n*(n-1)*...*1*1 | n |

**Example 3:** Consider the following function:

```
def bar(n):
for a in range(n):
for b in range(n):
print(a,b)
```

`bar(1)`

requires 1 print statements, while `bar(100)`

requires `100*100 = 10000`

print statements (each time `a`

increments, we have 100 print statements due to the inner for loop). Thus, the runtime increases **quadratically** proportional to the input. In other words, this function has a runtime complexity of Θ(`n^2`

).

input | function call | operations (prints) |
---|---|---|

1 | `bar(1)` |
1 |

2 | `bar(2)` |
4 |

... | ... | ... |

100 | `bar(100)` |
10000 |

... | ... | ... |

n | `bar(n)` |
n^2 |

**Example 4:** Consder the following function:

```
def rec(n):
if n == 0:
return 1
else:
return rec(n - 1) + rec(n - 1)
```

`rec(1)`

requires one addition, as it returns `rec(0) + rec(0)`

, and `rec(0)`

hits the base case and requires no further additions. but `rec(4)`

requires `2^4 - 1`

= 15 additions. To further understand the intuition, we can take a look at the recurisve tree below. To get `rec(4)`

, we need one addition. We have two calls to `rec(3)`

, which each require one addition, so this level needs two additions. Then we have four calls to `rec(2)`

, so this level requires four additions, and so on down the tree. In total, this adds up to 1 + 2 + 4 + 8 = 15 additions.

As we increase the input size of n, the runtime (number of operations) increases **exponentially** proportional to the input. In other words, this function has a runtime complexity of Θ(`2^n`

).

As an illustration, check out the table below:

input | function call | return value | operations |
---|---|---|---|

1 | `rec(1)` |
2 | 1 |

2 | `rec(2)` |
4 | 3 |

... | ... | ... | ... |

10 | `rec(10)` |
1024 | 1023 |

... | ... | ... | ... |

n | `rec(n)` |
`2^n` |
`2^n` |

Here are some general guidelines for finding the order of growth for the runtime of a function:

If the function is recursive or iterative, you can subdivide the problem as seen above:

- Count the number of recursive calls/iterations that will be made in terms of input size
`n`

. - Find how much work is done per recursive call or iteration in terms of input size
`n`

. - The answer is usually the product of the above two, but be sure to pay attention to control flow!

- Count the number of recursive calls/iterations that will be made in terms of input size
- If the function calls helper functions that are not constant-time, you need to take the runtime of the helper functions into consideration.
- We can ignore constant factors. For example
`1000000n`

and`n`

steps are both linear. - We can also ignore smaller factors. For example if
`h`

calls`f`

and`g`

, and`f`

is Quadratic while`g`

is linear, then`h`

is Quadratic. For the purposes of this class, we take a fairly coarse view of efficiency. All the problems we cover in this course can be grouped as one of the following:

- Constant: the amount of time does not change based on the input size. Rule:
`n --> 2n`

means`t --> t`

. - Logarithmic: the amount of time changes based on the logarithm of the input size. Rule:
`n --> 2n`

means`t --> t + k`

. - Linear: the amount of time changes with direct proportion to the size of the input. Rule:
`n --> 2n`

means`t --> 2t`

. - Quadratic: the amount of time changes based on the square of the input size. Rule:
`n --> 2n`

means`t --> 4t`

. - Exponential: the amount of time changes with a power of the input size. Rule:
`n --> n + 1`

means`t --> 2t`

.

- Constant: the amount of time does not change based on the input size. Rule:

# Required Questions

## Getting Started Videos

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your berkeley.edu email.

## Trees

### Q1: WWPD: Trees

Read over the `Tree`

class in `lab09.py`

. Make sure you understand the
doctests.

Use Ok to test your knowledge with the following "What Would Python Display?" questions:

`python3 ok -q trees-wwpd -u`

Enter

`Function`

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

,`Error`

if it errors, and`Nothing`

if nothing is displayed. Recall that`Tree`

instances will be displayed the same way they are constructed.

```
>>> from lab09 import *
>>> t = Tree(1, Tree(2))
______Error
>>> t = Tree(1, [Tree(2)])
>>> t.label
______1
>>> t.branches[0]
______Tree(2)
>>> t.branches[0].label
______2
>>> t.label = t.branches[0].label
>>> 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)])
```

### Q2: Make Even

Define a function `make_even`

which takes in a tree
`t`

whose values are integers, and mutates the tree such that all the
odd integers are increased by 1 and all the even integers remain the same.

```
def make_even(t):
"""
>>> t = Tree(1, [Tree(2, [Tree(3)]), Tree(4), Tree(5)])
>>> make_even(t)
>>> t.label
2
>>> t.branches[0].branches[0].label
4
"""
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q make_even`

### Q3: Cumulative Mul

Write a function `cumulative_mul`

that mutates the Tree `t`

so that each node's
label becomes the product of its label and all labels in the subtrees rooted at the node.

Hint: Consider carefully when to do the mutation of the tree and whether that mutation should happen before or after processing the subtrees.

```
def cumulative_mul(t):
"""Mutates t so that each node's label becomes the product of all labels in
the corresponding subtree rooted at t.
>>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
>>> cumulative_mul(t)
>>> t
Tree(105, [Tree(15, [Tree(5)]), Tree(7)])
>>> otherTree = Tree(2, [Tree(1, [Tree(3), Tree(4), Tree(5)]), Tree(6, [Tree(7)])])
>>> cumulative_mul(otherTree)
>>> otherTree
Tree(5040, [Tree(60, [Tree(3), Tree(4), Tree(5)]), Tree(42, [Tree(7)])])
"""
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q cumulative_mul`

### Q4: Prune Small

Complete the function `prune_small`

that takes in a `Tree`

`t`

and a
number `n`

and prunes `t`

mutatively. If `t`

or any of its branches
has more than `n`

branches, the `n`

branches with the smallest labels
should be kept and any other branches should be *pruned*, or removed,
from the tree.

Hint: The`max`

function takes in an`iterable`

as well as an optional`key`

argument (which takes in a one-argument function). For example,`max([-7, 2, -1], key = abs)`

would return`-7`

since`abs(-7)`

is greater than`abs(2)`

and`abs(-1)`

.

```
def prune_small(t, n):
"""Prune the tree mutatively, keeping only the n branches
of each node with the smallest labels.
>>> t1 = Tree(6)
>>> prune_small(t1, 2)
>>> t1
Tree(6)
>>> t2 = Tree(6, [Tree(3), Tree(4)])
>>> prune_small(t2, 1)
>>> t2
Tree(6, [Tree(3)])
>>> t3 = Tree(6, [Tree(1), Tree(3, [Tree(1), Tree(2), Tree(3)]), Tree(5, [Tree(3), Tree(4)])])
>>> prune_small(t3, 2)
>>> t3
Tree(6, [Tree(1), Tree(3, [Tree(1), Tree(2)])])
"""
while ___________________________:
largest = max(_______________, key=____________________)
_________________________
for __ in _____________:
___________________
```

Use Ok to test your code:

`python3 ok -q prune_small`

## Efficiency

### Q5: Orders of Growth

The following is a quick check on different orders of growth and runtimes that you'll run into in this class. You can refer to the orders of growth study guide for helpful hints regarding these questions!

Determine the order of growth of each of the functions specified below.

Choose one of:

- Constant
- Logarithmic
- Linear
- Quadratic
- Exponential
- None of these

Use Ok to test your understanding:

`python3 ok -q efficiency-quiz -u`

What is the *worst case* (i.e. when `n`

is prime) order of growth of `is_prime`

in terms of `n`

?

```
def is_prime(n):
for i in range(2, n):
if n % i == 0:
return False
return True
```

What is the order of growth of `bar`

in terms of `n`

?

```
def bar(n):
i, sum = 1, 0
while i <= n:
sum += biz(n)
i += 1
return sum
def biz(n):
i, sum = 1, 0
while i <= n:
sum += i**3
i += 1
return sum
```

What is the order of growth of `foo`

in terms of `n`

, where `n`

is the length
of `lst`

? Assume that slicing a list and calling `len`

on a list can both be
done in constant time.

```
def foo(lst, i):
mid = len(lst) // 2
if mid == 0:
return lst
elif i > 0:
return foo(lst[mid:], -1)
else:
return foo(lst[:mid], 1)
```

## Check Your Score Locally

You can locally check your score on each question of this assignment by running

`python3 ok --score`

**This does NOT submit the assignment!** When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

## Submit

Make sure to submit this assignment by uploading any files you've edited **to the appropriate Gradescope assignment.** For a refresher on how to do this, refer to Lab 00.

# Optional Questions

These questions are optional, but you must complete them in order to be checked off before the end of the lab period. They are also useful practice!

### Q6: Is BST

Write a function `is_bst`

, which takes a Tree `t`

and returns `True`

if, and
only if, `t`

is a valid binary search tree, which means that:

- Each node has at most two children (a leaf is automatically a valid binary search tree)
- The children are valid binary search trees
- For every node, the entries in that node's left child are less than or equal to the label of the node
- For every node, the entries in that node's right child are greater than the label of the node

An example of a BST is:

Note that, if a node has only one child, that child could be considered either the left or right child. You should take this into consideration.

*Hint:* It may be helpful to write helper functions `bst_min`

and `bst_max`

that
return the minimum and maximum, respectively, of a Tree if it is a valid binary
search tree.

```
def is_bst(t):
"""Returns True if the Tree t has the structure of a valid BST.
>>> t1 = Tree(6, [Tree(2, [Tree(1), Tree(4)]), Tree(7, [Tree(7), Tree(8)])])
>>> is_bst(t1)
True
>>> t2 = Tree(8, [Tree(2, [Tree(9), Tree(1)]), Tree(3, [Tree(6)]), Tree(5)])
>>> is_bst(t2)
False
>>> t3 = Tree(6, [Tree(2, [Tree(4), Tree(1)]), Tree(7, [Tree(7), Tree(8)])])
>>> is_bst(t3)
False
>>> t4 = Tree(1, [Tree(2, [Tree(3, [Tree(4)])])])
>>> is_bst(t4)
True
>>> t5 = Tree(1, [Tree(0, [Tree(-1, [Tree(-2)])])])
>>> is_bst(t5)
True
>>> t6 = Tree(1, [Tree(4, [Tree(2, [Tree(3)])])])
>>> is_bst(t6)
True
>>> t7 = Tree(2, [Tree(1, [Tree(5)]), Tree(4)])
>>> is_bst(t7)
False
"""
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q is_bst`

### Q7: Add trees

Define the function `add_trees`

, which takes in two trees and returns a new
tree where each corresponding node from the first tree is added with the node
from the second tree. If a node at any particular position is present in one
tree but not the other, it should be present in the new tree as well.

Hint:You may want to use the built-in zip function to iterate over multiple sequences at once.

```
def add_trees(t1, t2):
"""
>>> numbers = Tree(1,
... [Tree(2,
... [Tree(3),
... Tree(4)]),
... Tree(5,
... [Tree(6,
... [Tree(7)]),
... Tree(8)])])
>>> print(add_trees(numbers, numbers))
2
4
6
8
10
12
14
16
>>> print(add_trees(Tree(2), Tree(3, [Tree(4), Tree(5)])))
5
4
5
>>> print(add_trees(Tree(2, [Tree(3)]), Tree(2, [Tree(3), Tree(4)])))
4
6
4
>>> print(add_trees(Tree(2, [Tree(3, [Tree(4), Tree(5)])]), \
Tree(2, [Tree(3, [Tree(4)]), Tree(5)])))
4
6
8
5
5
"""
if _____________:
return _____________
if _____________:
return _____________
new_label = _____________
t1_branches, t2_branches = _____________
length_t1, length_t2 = _____________
if _____________:
t1_branches += [_____________]
elif _____________:
t2_branches += [_____________]
return _____________
```

Use Ok to test your code:

`python3 ok -q add_trees`