If there are fewer than 3 people in your group, merge your group with another group in the room. If your group has 6 or more students, you're welcome to split into two sub-groups and then sync up at the end. If you want two separate Pensieve documents for the two sub-groups, just have one sub-group add 1000 to their group number.

Now switch to Pensieve:

• Everyone: Go to pensieve.co, log in with your @berkeley.edu email, and enter your group number as the room number (which was in the email that assigned you to this discussion). As long as you all enter the same number (any number), you'll all be using a shared document.

Once you're on Pensieve, you don't need to return to this page; Pensieve has all the same content (but more features). If for some reason Penseive doesn't work, return to this page and continue with the discussion.

Attendance

Your TA will come around during discussion to check you in. You can start on the worksheet before being checked in; you don't need to wait for your TA to get started.

If you didn't attend for a good reason (such as being sick), fill out this form (within 2 weeks of your discussion): attendance form

Getting Started

Everyone go around and say your name.

For fun: Think of a big word with at least three syllables, such as "solitary" or "conundrum" or "ominous". Try to use it as many times as you can during today's discussion, but in ways that don't give away that it's your big word. At the end, your group will try to guess each person's big word. Whoever uses their big word the most times (and at least twice) without their group guessing it wins. (You win nothing; it's just a game.)

If there are fewer than 3 people in your group, feel free to merge your group with another group in the room.

Trees

For a tree t:

• Its root label can be any value, and label(t) returns it.
• Its branches are trees, and branches(t) returns a list of branches.
• An identical tree can be constructed with tree(label(t), branches(t)).
• You can call functions that take trees as arguments, such as is_leaf(t).
• That's how you work with trees. No t == x or t[0] or x in t or list(t), etc.
• There's no way to change a tree (that doesn't violate an abstraction barrier).

Here's an example tree t1, for which its branch branches(t1)[1] is t2.

t2 = tree(5, [tree(6), tree(7)])
t1 = tree(3, [tree(4), t2])

A path is a sequence of trees in which each is the parent of the next.

def tree(label, branches=[]):
    for branch in branches:
        assert is_tree(branch), 'branches must be trees'
    return [label] + list(branches)

def label(tree):
    return tree[0]

def branches(tree):
    return tree[1:]

def is_leaf(tree):
    return not branches(tree)

def is_tree(tree):
    if type(tree) != list or len(tree) < 1:
        return False
    for branch in branches(tree):
        if not is_tree(branch):
            return False
    return True

Q1: Warm Up

What value is bound to result?

result = label(min(branches(max([t1, t2], key=label)), key=label))

How convoluted! (That's a big word.)

>>> s = [-3, -5, -4, -1, -2]
>>> max(s)
-1
>>> max(s, key=abs)
-5
>>> max([abs(x) for x in s])
5

In case you're wondering, this expression does not violate an abstraction barrier. [t1, t2] and branches(t) are both lists (not trees), and so it's fine to call min and max on them.

Q2: Has Path

Implement has_path, which takes a tree t and a list p. It returns whether there is a path from the root of t with labels p. For example, t1 has a path from its root with labels [3, 5, 6] but not [3, 4, 6] or [5, 6].

Important: Before trying to implement this function, discuss these questions from lecture about the recursive call of a tree processing function:

• What small initial choice can I make (such as which branch to explore)?
• What recursive call should I make for each option?

• How can I combine the results of those recursive calls?

  • What type of values do they return?
  • What do those return values mean?

If you get stuck, you can view our answers to these questions by clicking the hint button below, but please don't do that until your whole group agrees.

If your group needs some guidance, you can click on the hints below, but please talk with your group first before reading the hints.

for ____:
    if ____:
        return True
return False

New Rule: Whoever in your group helped type the answer to the last question should not type the answer to the next one. Instead, just ask questions and give suggestions; give other members of your group a chance to type the answer.

Q3: Find Path

Implement find_path, which takes a tree t with unique labels and a value x. It returns a list containing the labels of the nodes along a path from the root of t to a node labeled x.

If x is not a label in t, return None. Assume that the labels of t are unique.

First talk through how to make and use the recursive call. (Try it yourselves; don't just click the hint button. That's how you learn.)

Please don't view the hints until you've discussed with your group and can't make progress.

Description Time! When your group has completed this question, it's time to describe why this function does not have a base case that uses is_leaf. If you can't figure it out, talk to a TA.

Big Word Search

For each person, the rest of the group should try to guess their big word (from the Getting Started section). The group only gets one guess. After they guess, reveal your big word and how many times you used it during discussion.

Optional Question

Tree problems often appear on exams. Here's one:

Q4: Only Paths

Implement only_paths, which takes a Tree of numbers t and a number n. It returns a new tree with only the nodes of t that are on a path from the root to a leaf with labels that sum to n, or None if no path sums to n.

Here is an illustration of the doctest examples involving t.