**Due by 4pm on Wednesday, 14 March**

You can grab a template for this homework either by downloading the file from the calendar or by running the following command in terminal on one of the school computers (the dot is significant: it denotes the current directory)

cp ~cs61a/lib/hw/hw8.py .

**Readings.** Chapter 3.3

**Q1.**
Write a version of `tree_find` from lecture (for finding keys among the
labels of a binary search tree) that is purely iterative and
does not use recursion.

**Q2.**
Define a function `depth` that, given a Tree, `T`, and a value, `x`,
finds the *depth* at which `x` appears as a label in the tree.
Depth here refers to distance from the root, `T`. The node `T` itself is
at depth 0; its children are at depth 1, etc. Assume that `x` appears at
most once in the tree. Return `None` if it does not appear.

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

- A node whose label is None represents an empty collection.
- Otherwise, there is at least one key in a node label and the keys are sorted in ascending order.
- A non-empty node with
Nkeys hasN+1children, which are also general search trees.- If x is key #k in a node's label, then all keys in child #k are less than x and all those in child #k+1 are greater than x.

Fill in the definition of `gen_tree_find` in the skeleton to search for
a key in such a general search tree.

**Q4.**
Write a higher-order function that generalizes memoization:

def memoize(func): """Returns a function that takes the same arguments as 'func' and returns the same value, but with memoization. That is, if f is the function returned by memoize(func), then f(v) returns func(v), but if f is called twice with the same arguments, v, it does not call func(v), but returns the previously returned value. We assume that 'func' is a pure function whose value depends only on the values of its arguments, and whose side-effects are irrelevant, and that the values of its argument, v, are of a type suitable for use as keys in a Python dictionary."""

So, for example, if we define:

def fib(x): print(x) if x <= 1: return 1 else: return fib(x-2) + fib(x-1) fib = memoize(fib)

and then call `fib(6)`, we'd get the expected return value (13), but the
printed values would be 0, 1, 2, 3, 4, 5, 6, instead of the sequence
we would expect from the unmemoized `fib`, which is 0, 1, 2, 0, 1, 3, 1, 2, 0, 1, etc.

Your `memoize` function should work with functions that take any
number of parameters. *Reminder:* In Python, the syntax:

def f(*a): ...

allows `f` to take any number of parameters (0 or more),
setting `a` to a tuple containing them. Likewise, if `g` is a function
taking two parameters, then:

>>> g(1, 2) 42 >>> v = (1, 2) >>> g(*v) 42

**Q5.**
Modify your solution to Q4 so that if the calculation of `func(v)` for some
value of `v` causes a recursive call of `func(v)` (that is, a call with the
same arguments, indicating an infinite loop), then the memoized function raises a `RuntimeError`
exception. Call the new version `checked_memoize`.

**Q6.**
Consider the following definition of `adjoin_set`, adapted to the
binary search trees in this problem set, and `adjoin_all`:

empty_set = Tree(None) def adjoin_set(S, v): """Assuming S is a binary search tree representing a set (no duplicate values), the binary search tree representing the set S U {v}.""" if S.label is None: return Tree(v, None, None) elif v < S.label: return Tree(S.label, adjoin_set(S[0], v), S[1]) elif v == S.label: return S else: return Tree(S.label, S[0], adjoin_set(S[1], v)) def adjoin_all(S, L): """The result of adding all the elements of L to set S, in order.""" for v in L: S = adjoin_set(v) return S

Define two functions: `bad(N)` and `good(N)` that each returns a sequence of
`N` non-null integer values such that `tree_find(adjoin_all(empty_set, bad(N)), x)` takes as long as possible for any given value `N` and the worst
`x`, and `tree_find(adjoin_all(empty_set, good(N)), x)` takes as little time as
possible for any given value `N` and the worst `x`.

**Q7.** [Extra for experts]
Write a function that returns the result of *removing* a value
from a binary search tree, if it is present (maintaining the search-tree
property, of course). 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.

**Q8.** [Extra for experts] Define a function `preorder(T)` on Trees
that returns an iterator over the labels in T in preorder. That
is, it lists a node's label first, then those of its children
(recursively) in order. (For this problem, there are no empty trees;
None is just a possible label value):

""" >>> T = Tree(1, Tree(2, Tree(3, 4, 5), 6), 7, 8) >>> list(preorder(T)) [1, 2, 3, 4, 5, 6, 7, 8] """