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

**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 `hw6.py`. Follow the instructions here to submit the electronic copy.

**Readings.** All problems in this homework can be solved
with the subset of Python 3 introduced in sections 1-2.4 of the
lecture notes.

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

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

cp ~cs61a/lib/hw/hw06/hw6.py .

to copy it into your current directory.

In this homework we will be using the itree abstract
data type. The file `itree.py`

defines this ADTs along with some
useful utility functions for manipulating them. On the lab computers, you
should be able to import from these modules without any additional setup.
**READ THIS FILE!** It contains functions we might not have
introduced in lecture that might or might not be useful for solving these
questions.

**Q1.** Define a function `depth` that, given an ITree, `t`,
and a value, `v`, finds the *depth* at
which `v` appears as a datum 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 `v` appears at
most once in the tree. Return `None` if it does
not appear.

**Q2.** Define a function `prune_leaves` that, given an ITree, `t`, and a tuple of values, `vals`,
and produces a tree with all leaves that contain one of the items in `vals` removed. Do **not** attempt
to try to remove non-leaf nodes and do **not** remove leaves that
do not match any of the items in `vals`. If you
have to remove the root of a tree, return None.

**Q3.** Define a function `sprout_leaves` that, given an ITree, `t`, and a tuple of values, `vals`,
and produces a tree with every leaf having new children that contain each of the
items in `vals`. Do **not** add
new children to non-leaf nodes.

**Q4.** Define a function `same_shape` that, given two ITrees, `t1` and `t2`, returns `True` if the two trees have the same shape (but not
necessarily the same data in each node) and `False` otherwise.

**Q5.** A mobile is a type of hanging sculpture. For
example, here is a picture of a
mobile created by Alexander Calder.

A simple binary mobile consists of two branches, left and right. Each
branch is a rod of a certain length, from which hangs either a weight or another
mobile. Such a mobile is balanced (meaning that it will not fall over to one
side and will hang horizontally) if every "sub-mobile" (the mobiles that hang to
the left or the right) is balanced and the product of the length of the left
branch times the *total* weight on the left branch is equal to the
product of the length of the right branch times the *total* weight on the
right branch.

In the template file `hw6.py`

we have implemented abstract
data types for representing mobiles and branches. Using these abstract data
types, implement the functions `total_weight`,
which finds the total weight of a mobile, and `is_balanced`, which takes a mobile `m` and returns True if the mobile is properly balanced.