*Due by 11:59 PM on (that is, the end of) Saturday, 7/14*

**This homework must be submitted online.** We do not
require a paper copy. If you would like a reader to give you written feedback
on your homework, submit a paper copy to the homework box.

**To turn in the electronic copy**, submit all of your
answers in a file named `hw7.py`. Follow the instructions here to submit the electronic copy.

If you would like, you can use the template file `hw7.py`

.
To copy this file to your lab account you can run the command:

cp ~cs61a/lib/hw/hw07/hw7.py .

to copy it into your current directory.

In this and future homeworks, we have three different categories of questions:

**Core Questions**— Questions that we believe test a core concept of the course and should be your highest priority when attempting the homework.**Reinforcement Questions**— Questions that we believe have material that is either covered by other questions in this homework or in past homeworks, and can therefore be considered second priority after the core questions have been completed.**Extra for Experts**— As in earlier homeworks, these problems are*completely optional*. You are encouraged to try these questions once you have completed questions from the other two categories. However, these are questions that we consider either more difficult than what we would ask you on an exam or that focus on ideas we are not concerned with in this course, so please do not be discouraged if you do not solve them.

It is our hope that these categories will help guide you in deciding how to divide your time when working on the homeworks.

For the first question of this homework we will work with the
binary search tree data abstraction as defined in
`bst.py`

. For the third question, we will
use a new general search tree data abstraction, provided in
`gst.py`

, which uses code from
`itree.py`

.

**Core Questions**

**Q1**. In this question, we will generalize the idea of
binary search trees to handle *any method* of sorting items.
We will generalize the method `bst_find`
to `bst_gen_find` to handle items more
general than simple numbers by using an additional argument
`compare_fn`.
`compare_fn` is a comparison function
that takes two values and compares them by returning
`-1` if the first argument
is "less than" the second, `0` if
the two are "equal", and `1` if the
first argument is "greater than" the second argument.
*Hint*: We have provided the generalized version of
`bst_insert` as
`bst_gen_insert`, which also
takes `compare_fn` as an argument.

**Q2**. Create a class called `VendingMachine` that represents a vending machine for
some product. A `VendingMachine`
object does not actually return anything but strings describing its
interactions. See the class doctest for examples.
(In Nanjing, there are even vending machines for
live crabs.)

**Reinforcement Questions**

**Q3**. Generalize the binary search trees from lecture
to search trees with more than two children. We can define a
*general search tree* (GST) as one whose labels are *tuples*
of keys such that

- A node whose datum is
Nonerepresents an empty general search tree.- Otherwise, there is at least one key in the datum of a node and the keys are stored in a tuple sorted in
ascending order.- A non-empty node with
Nkeys hasN+1children, which are also general search trees.- The
N+1children are stored in a tuple in a specific order: Ifxis key numberkin a node's datum, then all the keys in the children GST at position numberskand below (of the children tuple) are less thanxand all those in children GST at position numbersk+1(of the children tuple) and above are greater thanx.

We have provided you a data abstraction for GSTs (which is not a
standard term) in `gst.py`

. Using the abstraction provided,
fill in the definition of `gst_find`
in `hw7.py`

to search for a key in a GST.

**Extra for Experts**

**Q4**. Write a function
`bst_remove` that returns the result of
*removing* a value from a binary search tree, if it is present
(maintaining the search-tree property, of course). The function returns
the original tree if the value is not present. The time spent should be
proportional to the depth of the tree.
*Hint*: This is easy if the node whose label matches the value
being deleted contains at most one non-empty child. The tricky part is
figuring out what to do when that node has two non-empty children.