Solution Files

You can find the solutions in hw09.py.

Required Questions

Trees

Q1: Square

Write a function label_squarer that mutates a Tree with numerical labels so that each label is squared.

def label_squarer(t):
    """Mutates a Tree t by squaring all its elements.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> label_squarer(t)
    >>> t
    Tree(1, [Tree(9, [Tree(25)]), Tree(49)])
    """
    t.label = t.label ** 2
    for subtree in t.branches:
        label_squarer(subtree)

Use Ok to test your code:

python3 ok -q label_squarer
Copy
✂️

Q2: Preorder

Define the function preorder, which takes a Tree instance and returns a list of all the labels in the tree in the order that they appear when the tree is printed.

The following diagram shows the order that the nodes would get printed, with the arrows representing function calls.

This ordering of the nodes in a tree is called a preorder traversal.

def preorder(t):
    """Return a list of the entries in this tree in the order that they
    would be visited by a preorder traversal (see problem description).

    >>> numbers = Tree(8, [Tree(2), Tree(9, [Tree(4), Tree(5)]), Tree(6, [Tree(7)])])
    >>> print(numbers)
    8
      2
      9
        4
        5
      6
        7
    >>> preorder(numbers)
    [8, 2, 9, 4, 5, 6, 7]
    """
    labels = [t.label]
    for b in t.branches:
        labels.extend(preorder(b))
    return labels

Use Ok to test your code:

python3 ok -q preorder
Copy
✂️

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.