# Study Guide: Mutable Trees

## Instructions

This is the companion guide to Quiz 7 with links to past lectures, assignments, and handouts, as well as isomorphic quiz problems and additional practice problems to assist you in learning the concepts.

**Assignments**

**Handouts**

**Lectures**

**Readings**

# Guides

## Mutable Trees

Trees are a hierarchical data structure. Previously in this class, we
represented tree-like structures using functional abstraction with the `tree`

constructor and `label`

and `branches`

selectors. If we wanted to 'change' the
values in the `tree`

abstraction, we would need to create an entirely new tree
with the desired values.

But classes allow us to modify the values in a tree in-place using mutation,
without needing to create new objects. We can reassign to `t.label`

or
`t.branches`

, things that we couldn't do previously with the `tree`

functional
abstraction.

```
>>> t = Tree(1)
>>> t.label
1
>>> t.label = 2
>>> t.label
2
```

The best way to model trees is by drawing tree diagrams like we saw in lecture. Each node in a tree is represented with a circle and contains its label value and a list of branches.

All of our previous knowledge of trees still applies. The tree problems that we
usually try to solve still involve tree traversal where we visit each node in
the tree and perform some computations as we visit. For example, we can define
a function `square_tree`

which takes in a mutable `Tree`

and squares each value
in the tree.

```
def square_tree(t):
t.label = t.label ** 2
for b in t.branches:
square_tree(b)
```

But tree mutation problems can come in many different shapes and forms and require us to pay special attention to fundamentals like domain and range.

For example, here are two ways of defining a function, `prune_2`

, which removes
the last two branches of each node in the tree. The general strategy is to
replace each node's branches with a new list of branches containing only the
desired branches. One way to do this would be to call `prune_2`

on each branch
we'd like to keep.

```
def prune_2(t):
t.branches = [prune_2(b) for b in t.branches[:2]]
return t
```

Notice that we had to return the input tree, `t`

. Why is this necessary?

Another way would be to first prune the branches, and then loop over the remaining branches. This has the advantage that it makes it clear to the person using this program that a new tree is not created.

```
def prune_2(t):
t.branches = t.branches[:2]
for b in t.branches:
prune_2(b)
```

# Practice Problems

## Easy

### Q1: Leaves

Write a function `leaves`

that returns a list of all the label values of the
leaf nodes of a `Tree`

.

```
def leaves(t):
"""Returns a list of all the labels 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.label]
all_leaves = []
for b in t.branches:
all_leaves += leaves(b)
return all_leaves
```

Use Ok to test your code:

`python3 ok -q leaves`

### Q2: 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 and only if they have the same number
of branches and each pair of corresponding 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 iff they have the same number of branches and each pair
of corresponding branches 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(3, [Tree(2, [Tree(1)])])])
>>> same_shape(t, s)
False
"""
"*** YOUR CODE HERE ***"
return len(t1.branches) == len(t2.branches) and \
all([same_shape(b1, b2) for b1, b2 in zip(t1.branches, t2.branches)])
```

Use Ok to test your code:

`python3 ok -q same_shape`

## Medium

### Q3: Prune Min

Write a function that prunes a `Tree`

`t`

mutatively. `t`

and its branches
always have zero or two branches. For the trees with two branches, reduce the
number of branches from two to one by keeping the branch that has the smaller
label value. Do nothing with trees with zero branches.

Prune the tree from the bottom up. The result should be a linear tree.

```
def prune_min(t):
"""Prune the tree mutatively from the bottom up.
>>> t1 = Tree(6)
>>> prune_min(t1)
>>> t1
Tree(6)
>>> t2 = Tree(6, [Tree(3), Tree(4)])
>>> prune_min(t2)
>>> t2
Tree(6, [Tree(3)])
>>> t3 = Tree(6, [Tree(3, [Tree(1), Tree(2)]), Tree(5, [Tree(3), Tree(4)])])
>>> prune_min(t3)
>>> t3
Tree(6, [Tree(3, [Tree(1)])])
"""
"*** YOUR CODE HERE ***"
if t.branches == []:
return
prune_min(t.branches[0])
prune_min(t.branches[1])
if (t.branches[0].label > t.branches[1].label):
t.branches.pop(0)
else:
t.branches.pop(1)
```