Due by 11:59pm on Wednesday, November 20

Instructions

Download hw09.zip. Inside the archive, you will find a file called hw09.py, along with a copy of the ok autograder.

Submission: When you are done, submit the assignment by uploading all code files you've edited to Gradescope. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on Gradescope. See Lab 0 for more instructions on submitting assignments.

Using Ok: If you have any questions about using Ok, please refer to this guide.

Readings: You might find the following references useful:

• Section 2.9.2

Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. This homework is out of 2 points.

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)])
    """
    "*** YOUR CODE HERE ***"

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]
    """
    "*** YOUR CODE HERE ***"

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.