If you need help reviewing Mutable Trees, take a look at these resources:

We will be using the OOP implementation of `Tree`

s from lecture,
found
here

Each question has a "Toggle Solution" button -- click it to reveal that question's solution.

## Trees

### Question 1

Implement a function `equal`

which takes two trees and returns `True`

if they satisfy all the following conditions:

- The data of both Trees are equal
- The Trees have the same number of children
All corresponding pairs of sub-Trees are also

`equal`

def equal(t1, t2):

`"""Returns Tree if t1 and t2 are equal trees. >>> t1 = Tree(1, ... [Tree(2, [Tree(4)]), ... Tree(3)]) >>> t2 = Tree(1, ... [Tree(2, [Tree(4)]), ... Tree(3)]) >>> equal(t1, t2) True >>> t3 = Tree(1, ... [Tree(2), ... Tree(3, [Tree(4)])]) >>> equal(t1, t3) False """ "*** YOUR CODE HERE ***"`

```
def equal(t1, t2):
if t1.entry != t2.entry:
return False
elif len(t1.subtrees) != len(t2.subtrees):
return False
else:
return all(equal(child1, child2) for child1, child2
in zip(t1.subtrees, t2.subtrees))
```

### Question 2

Implement a function `size`

that returns the number of elements in a
given Tree.

```
def size(t):
"""Returns the number of elements in a tree.
>>> t1 = Tree(1,
... [Tree(2, [Tree(4)]),
... Tree(3)])
>>> size(t1)
4
"""
"*** YOUR CODE HERE ***"
```

```
def size(t):
return 1 + sum([size(child) for child in t.subtrees])
```

### Question 3

Implement a function `height`

, which returns the height of a Tree. The
*height* of a tree is defined as the number of branches from the
*root* to the bottom-most *leaf* of the Tree.

By definition, a leaf has a height of 0, since there are 0 branches from the root to the root.

```
def height(t):
"""Returns the height of the tree.
>>> leaf = Tree(1)
>>> height(leaf)
0
>>> t1 = Tree(1,
... [Tree(2, [Tree(4)]),
... Tree(3)])
>>> height(t1)
2
"""
"*** YOUR CODE HERE ***"
```

```
def height(t):
if len(t.subtrees) == 0:
return 0
return 1 + max([height(child) for child in t.subtrees])
```

### Question 4

Implement a function `same_shape`

, which takes two `Tree`

s and returns
True if the trees have the same structure, but not necessarily the same
entries.

```
def same_shape(t1, t2):
"*** YOUR CODE HERE ***"
```

```
def same_shape(t1, t2):
if not t1.subtrees or not t2.subtrees:
return not t1.subtrees and not t2.subtrees
elif len(t1.subtrees) != len(t2.subtrees):
return False
for i in range(len(t1.subtrees)):
if not same_shape(t1.subtrees[i], t2.subtrees[i]):
return False
return True
```

### Question 5

Implement a function `sprout_leaves`

, which takes a `Tree`

and a list
of values. For every leaf of the `Tree`

, mutate it so that it has a
list of branches where the items are the elements in the list of
values.

```
def sprout_leaves(t, vals):
"*** YOUR CODE HERE ***"
```

```
def sprout_leaves(t, vals):
if not t.subtrees:
t.subtrees = [Tree(v) for v in vals]
else:
for branch in t.subtrees:
sprout_leaves(branch, vals)
```

### Question 6

Implement a function `prune_leaves`

, which takes a `Tree`

and a list
of values. For every leaf of the `Tree`

, remove it if its entry is in
the list of values.

```
def prune_leaves(t, vals):
"*** YOUR CODE HERE ***"
```

```
def prune_leaves(t, vals):
if not t.subtrees:
if t.entry not in vals:
return t
else:
return None
new_branches = [prune_leaves(branch, vals) for branch in t.subtrees]
t.subtrees = [b for b in new_branches if b is not None]
return t
```

## Binary Search Trees

### Question 7

Implement two functions, `max_bst`

and `min_bst`

, which take a binary
search tree and returns the maximum and minimum values, respectively.

```
def max_bst(b):
"*** YOUR CODE HERE ***"
```

```
def max_bst(b):
if b.right.is_empty:
return b.entry
return max_bst(b.right)
```

```
def min_bst(b):
"*** YOUR CODE HERE ***"
```

```
def min_bst(b):
if b.left.is_empty:
return b.entry
return min_bst(b.left)
```

### Question 8

Implement the function `contains`

, which takes a binary search tree and
an item, and returns True if the binary search tree contains the item,
and False if it doesn't.

```
def contains(b, item):
"""Returns True if B contains ITEM.
>>> b1 = Tree(2,
... Tree(1),
... Tree(4, Tree(3)))
>>> contains(b1, 4)
True
>>> contains(b1, 8)
False
"""
"*** YOUR CODE HERE ***"
```

```
def contains(b, item):
if b is None:
return False
elif b.entry == item:
return True
elif b.entry > item:
return contains(b.left, item)
elif b.entry < item:
return contains(b.right, item)
```

### Question 9

Implement the function `in_order`

, which takes a binary search tree,
and returns a list containing its items from smallest to largest. In
computer science, this is known as an **in-order traversal**.

```
def in_order(b):
"""Returns the items in B, a binary search tree, in sorted
order.
>>> b1 = Tree(2,
... Tree(1),
... Tree(4, Tree(3)))
>>> in_order(b1)
[1, 2, 3, 4]
>>> singleton = Tree(4)
>>> in_order(singleton)
[4]
"""
"*** YOUR CODE HERE ***"
```

```
def in_order(b):
if b is None:
return []
else:
left = in_order(b.left)
right = in_order(b.right)
return left + [b.entry] + right
```

### Question 10

Implement a function `nth_largest`

, which takes a **binary search
tree** and a number `n`

(greater than or equal to 1), and returns the
`nth`

largest item in the tree. For example, `nth_largest(b, 1)`

should
return the largest item in `b`

. If `n`

is greater than the number of
items in the tree, return None.

**Hint**: You can assume there is a `size`

function that returns the
number of elements in a given tree.

```
def nth_largest(b, n):
"""Returns the Nth largest item in T.
>>> b1 = Tree(2,
... Tree(1),
... Tree(4, Tree(3)))
>>> nth_largest(b1, 1)
4
>>> nth_largest(b1, 3)
2
>>> nth_largest(b1, 4)
1
"""
"*** YOUR CODE HERE ***"
```

```
def nth_largest(b, n):
if b is None:
return None
right = size(b.right)
if right == n - 1:
return b.entry
elif right > n - 1:
return nth_largest(b.right, n)
elif right < n - 1:
return nth_largest(b.left, n - 1 - right)
```