Lab 9: Trees

Due by 11:59pm on Friday, November 7.

Starter Files

Download lab09.zip.

Topics

Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.


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:

- Tree constructor and selector functions Tree class
Constructing a tree To construct a tree given a label and a list of branches, we call tree(label, branches) To construct a tree object given a label and a list of branches, we call Tree(label, branches) (which calls the Tree.__init__ method).
Label and branches To get the label or branches of a tree t, we call label(t) or branches(t) respectively To get the label or branches of a tree t, we access the instance attributes t.label or t.branches respectively.
Mutability The functional tree data abstraction is immutable (without violating its abstraction barrier) because we cannot assign values to call expressions The label and branches attributes of a Tree instance can be reassigned, mutating the tree.
Checking if a tree is a leaf To check whether a tree t is a leaf, we call the function is_leaf(t) To check whether a tree t is a leaf, we call the method t.is_leaf(). This method can only be called on Tree objects.

WWPD

Q1: WWPD: Trees

Read over the Tree class in lab08.py. Make sure you understand the doctests.

Use Ok to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q trees-wwpd -u

Enter Function if you believe the answer is <function ...>, Error if it errors, and Nothing if nothing is displayed. Recall that Tree instances will be displayed the same way they are constructed.

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

______
Error

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

______
1

>>> t.branches[0]

______
Tree(2)

>>> t.branches[0].label

______
2

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

______
Tree(2, [Tree(2)])

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

______
2

>>> t.branches[0]

______
Tree(2)

>>> t.branches[1]

______
Tree(4, [Tree(8)])

Required Questions

Q2: Maximum Path Sum

Write a function that takes in a tree and returns the maximum sum of the values along any path from the root to a leaf of the tree.

def max_path_sum(t):
    """Return the maximum path sum of the tree.

    >>> t = Tree(1, [Tree(5, [Tree(1), Tree(3)]), Tree(10)])
    >>> max_path_sum(t)
    11
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q max_path_sum

Q3: Find Path

Write a function that takes in a tree with unique labels (no repeats) and a value x and returns a list containing the nodes along the path required to get from the root of the tree to the node containing x.

If x is not present in the tree, return None.

For the following tree, find_path(t, 5) should return [2, 7, 6, 5]

Example Tree

def find_path(t, x):
    """
    >>> t = Tree(2, [Tree(7, [Tree(3), Tree(6, [Tree(5), Tree(11)])]), Tree(15)])
    >>> find_path(t, 5)
    [2, 7, 6, 5]
    >>> find_path(t, 10)  # returns None
    """
    if ____:
        return ____
    for b in t.branches:
        path = ____
        if path:
            return ____

Use Ok to test your code:

python3 ok -q find_path

Q4: Prune Small

Removing some nodes from a tree is called pruning the tree.

Complete the function prune_small that takes in a Tree t and a number n. For each node with more than n branches, keep only the n branches with the smallest labels and remove (prune) the rest.

Hint: The max function takes in an iterable as well as an optional key argument (which takes in a one-argument function). For example, max([-7, 2, -1], key=abs) would return -7 since abs(-7) is greater than abs(2) and abs(-1).

def prune_small(t, n):
    """Prune the tree mutatively, keeping only the n branches
    of each node with the smallest labels.

    >>> t1 = Tree(6)
    >>> prune_small(t1, 2)
    >>> t1
    Tree(6)
    >>> t2 = Tree(6, [Tree(3), Tree(4)])
    >>> prune_small(t2, 1)
    >>> t2
    Tree(6, [Tree(3)])
    >>> t3 = Tree(6, [Tree(1), Tree(3, [Tree(1), Tree(2), Tree(3)]), Tree(5, [Tree(3), Tree(4)])])
    >>> prune_small(t3, 2)
    >>> t3
    Tree(6, [Tree(1), Tree(3, [Tree(1), Tree(2)])])
    """
    while ____:
        largest = max(____, key=____)
        ____
    for b in t.branches:
        ____

Use Ok to test your code:

python3 ok -q prune_small

Check Your Score Locally

You can locally check your score on each question of this assignment by running

python3 ok --score

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

Submit Assignment

Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.