Discussion 7: Mutable Trees

• disc07.pdf

Attendance

Your TA will come around during discussion to check you in.

If you miss discussion for a good reason (such as sickness or a scheduling conflict), email cs61a@berkeley.edu within one week to receive attendance credit.

Mutable Trees

A Tree instance has two instance attributes:

• label is the value stored at the root of the tree.
• branches is a list of Tree instances that hold the labels in the rest of the tree.

The Tree class (with its __repr__ and __str__ methods omitted) is defined as:

class Tree:
    """A tree has a label and a list of branches.

    >>> t = Tree(3, [Tree(2, [Tree(5)]), Tree(4)])
    >>> t.label
    3
    >>> t.branches[0].label
    2
    >>> t.branches[1].is_leaf()
    True
    """
    def __init__(self, label, branches=[]):
        self.label = label
        for branch in branches:
            assert isinstance(branch, Tree)
        self.branches = list(branches)

    def is_leaf(self):
        return not self.branches

To construct a Tree instance from a label x (any value) and a list of branches bs (a list of Tree instances) and give it the name t, write t = Tree(x, bs).

For a tree t:

• Its root label can be any value, and t.label evaluates to it.
• Its branches are always Tree instances, and t.branches evaluates to the list of its branches.
• t.is_leaf() returns True if t.branches is empty and False otherwise.
• To construct a leaf with label x, write Tree(x).

Displaying a tree t:

• repr(t) returns a Python expression that evaluates to an equivalent tree.
• str(t) returns one line for each label indented once more than its parent with children below their parents.

>>> t = Tree(3, [Tree(1, [Tree(4), Tree(1)]), Tree(5, [Tree(9)])])

>>> t         # displays the contents of repr(t)
Tree(3, [Tree(1, [Tree(4), Tree(1)]), Tree(5, [Tree(9)])])

>>> print(t)  # displays the contents of str(t)
3
  1
    4
    1
  5
    9

Changing (also known as mutating) a tree t:

• t.label = y changes the root label of t to y (any value).
• t.branches = ns changes the branches of t to ns (a list of Tree instances).
• Mutation of t.branches will change t. For example, t.branches.append(Tree(y)) will add a leaf labeled y as the right-most branch.
• Mutation of any branch in t will change t. For example, t.branches[0].label = y will change the root label of the left-most branch to y.

>>> t.label = 3.0
>>> t.branches[1].label = 5.0
>>> t.branches.append(Tree(2, [Tree(6)]))
>>> print(t)
3.0
  1
    4
    1
  5.0
    9
  2
    6

Here is a summary of the differences between the tree data abstraction implemented as a functional abstraction vs. implemented as a class:

Q1: WWPD: Trees

What would Python display?

>>> t = Tree(1, Tree(2))

Your Answer:

>>> t = Tree(1, [Tree(2)])
>>> t.label

Your Answer:

>>> t.label *= 4
>>> t

Your Answer:

>>> t.branches[0]

Your Answer:

>>> t.branches[0].label

Your Answer:

>>> t.label = t.branches[0].label
>>> t

Your Answer:

>>> t.branches.append(Tree(4, [Tree(8)]))
>>> len(t.branches)

Your Answer:

>>> t.branches[0]

Your Answer:

>>> t.branches[1]

Your Answer:

Working with the Tree class

Q2: Widest Level

Write a function that takes a Tree object and returns the elements at the depth with the most elements. In the case of a tie between two depths with the same number of elements, pick the lower depth.

In this problem, you may find it helpful to use the second optional argument to sum, which provides a starting value. All items in the sequence to be summed will be concatenated to the starting value. By default, start will default to 0, which allows you to sum a sequence of numbers. We provide an example of sum starting with a list, which allows you to concatenate items in a list.

Q3: Long Paths

Implement long_paths, which returns a list of all paths in a tree with length at least n. A path in a tree is a list of node labels that starts with the root and ends at a leaf. Each subsequent element must be from a label of a branch of the previous value's node. The length of a path is the number of edges in the path (i.e. one less than the number of nodes in the path). Paths are ordered in the output list from left to right in the tree. See the doctests for some examples.

Mutating Trees

Q4: Level Mutation

As a reminder, the depth of a node is how far away the node is from the root. We define this as the number of edges between the root to the node. As there are no edges between the root and itself, the root has depth 0.

Given a tree t and a list of one-argument functions funcs, write a function that will mutate the labels of t using the function from funcs at the corresponding depth. For example, the label at the root node (with a depth of 0) will be mutated using the function at index 0, or funcs[0]. Assume all of the functions in funcs will be able to take in a label value and return a valid label value.

If t is a leaf and there are more than 1 functions in funcs, all of the remaining functions should be applied in order to the label of t. (See the doctests for an example.) If funcs is empty, the tree should remain unmodified.

Q5: Delete

Implement delete, which takes a Tree t and removes all non-root nodes labeled x. The parent of each remaining node is its nearest ancestor that was not removed. In other words, when a non-leaf node is deleted, the deleted node's children become children of its parent. The root node is never removed, even if its label is x.