Homework 9
Due at 11:59:59 pm on Thursday, 04/20/2023.

Instructions

Download hw09.zip. Inside the archive, you will find starter files for the questions in this homework, along with a copy of the OK autograder.

Submission: When you are done, submit with python3 ok --submit. 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 okpy.org.

Readings: This homework relies on following references:

• Section 2.9.1

Trees

Our Tree consists of an value and a list of its branches. To create a tree and access its root and branches, use the following constructor and selectors:

• Constructor

  • Tree(value, branches): creates a tree object with the given root and list of branches. You can also call it with no branches to make a leaf, just like we saw with links.

• Selectors

  • tree.value: returns the value of the root of the tree.
  • tree.branches: returns the list of branches of the given tree.
  • tree.is_leaf(): returns True if tree's list of branches is empty, and False otherwise. Notice this is a function call

For example, the tree generated by

t = Tree(1, [Tree(2),
             Tree(3, [Tree(4), Tree(5)]),
             Tree(6, [Tree(7)])])

would look like this:

   1
 / | \
2  3  6
  / \  \
 4   5  7

It may be easier to visualize this translation by formatting the code like this:

t = Tree(1,
         [Tree(2),
          Tree(3,
               [Tree(4),
                Tree(5)]),
          Tree(6,
               [Tree(7)])])

To extract the number 3 from this tree, which is the value of the root of its second branch, we would do this:

t.branches[1].value

Here is the implementation of the tree class, with the __repr__ function giving you what you need to type to create a tree when you enter an instance of the tree into the interpreter, and the __str__ function giving you a pretty version of a tree when you print it.

class Tree:
    def __init__(self, value, branches=()):
        self.value = value
        for branch in branches:
            assert isinstance(branch, Tree)
        self.branches = list(branches)

    def __repr__(self):
        if self.branches:
            branches_str = ', ' + repr(self.branches)
        else:
            branches_str = ''
        return 'Tree({0}{1})'.format(self.value, branches_str)

    def __str__(self):
        def print_tree(t, indent=0):
            tree_str = '  ' * indent + str(t.value) + "\n"
            for b in t.branches:
                tree_str += print_tree(b, indent + 1)
            return tree_str
        return print_tree(self).rstrip()

    def is_leaf(self):
        return not self.branches

Question 1: Leaves

Write a function leaves that returns a list of all the values of the leaf nodes of a Tree.

def leaves(t):
    """Returns a list of all the entries of the leaf nodes of the Tree t.

    >>> leaves(Tree(1))
    [1]
    >>> leaves(Tree(1, [Tree(2, [Tree(3)]), Tree(4)]))
    [3, 4]
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q leaves

Question 2: Square Tree

Write a function square_tree that mutates a Tree with numerical entries so that each entry is squared.

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

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> square_tree(t)
    >>> t
    Tree(1, [Tree(9, [Tree(25)]), Tree(49)])
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q square_tree

Question 3: Path

Write a function path that returns the path from the root of the tree to the given value target as a list if it exists and [] if it does not. You can assume all values are unique.

def path(t, target):
    """
    >>> t = Tree(9, [Tree(7, [Tree(3), Tree(2)]), Tree(5)])
    >>> path(t, 2)
    [9, 7, 2]
    >>> path(t, 5)
    [9, 5]
    >>> path(t, 8)
    []
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q path

Question 4: Find Level

Implement find_level, which takes a tree t and an integer level and returns a list of all the values that have depth level. If no such values exist, return the empty list. For a refresher on the depth of a node, check out here.

def find_level(t, level):
    """
    >>> t = Tree(1, [Tree(2, [Tree(4), Tree(5)]), Tree(6, [Tree(7)])])
    >>> find_level(t, 2)
    [4, 5, 7]
    >>> find_level(t, 1)
    [2, 6]
    >>> find_level(t, 5)
    []
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q find_level

Submit

Make sure to submit this assignment by running:

python3 ok --submit