# Mutable Trees: exam-level questions

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)``````