Homework 5: Trees, Linked Lists

Due by 11:59pm on Thursday, July 28

Instructions

Download hw05.zip. Inside the archive, you will find a file called hw05.py, 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. 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:

Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. There is a homework recovery policy as stated in the syllabus. This homework is out of 2 points.

Required Questions


Getting Started Videos

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your berkeley.edu email.

YouTube link

Code Writing Questions

Q1: Add Leaves

Implement add_d_leaves, a function that takes in a Tree instance t and a number v.

We define the depth of a node in t to be the number of edges from the root to that node. The depth of root is therefore 0.

For each node in the tree, you should add d leaves to it, where d is the depth of the node. Every added leaf should have a label of v. If the node at this depth has existing branches, you should add these leaves to the end of that list of branches.

For example, you should be adding 1 leaf with label v to each node at depth 1, 2 leaves to each node at depth 2, and so on.

Here is an example of a tree t(shown on the left) and the result after add_d_leaves is applied with v as 5. add

Try drawing out the second doctest to visualize how the function is mutating t3.

Hint: Use a helper function to keep track of the depth!

def add_d_leaves(t, v):
    """Add d leaves containing v to each node at every depth d.

    >>> t_one_to_four = Tree(1, [Tree(2), Tree(3, [Tree(4)])])
    >>> print(t_one_to_four)
    1
      2
      3
        4
    >>> add_d_leaves(t_one_to_four, 5)
    >>> print(t_one_to_four)
    1
      2
        5
      3
        4
          5
          5
        5

    >>> t1 = Tree(1, [Tree(3)])
    >>> add_d_leaves(t1, 4)
    >>> t1
    Tree(1, [Tree(3, [Tree(4)])])
    >>> t2 = Tree(2, [Tree(5), Tree(6)])
    >>> t3 = Tree(3, [t1, Tree(0), t2])
    >>> print(t3)
    3
      1
        3
          4
      0
      2
        5
        6
    >>> add_d_leaves(t3, 10)
    >>> print(t3)
    3
      1
        3
          4
            10
            10
            10
          10
          10
        10
      0
        10
      2
        5
          10
          10
        6
          10
          10
        10
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q add_d_leaves

Q2: Has Path

Write a function has_path that takes in a Tree t and a string target. It returns True if there is a path that starts from the root where the entries along the path spell out the target, and False otherwise. You may assume that every node's label is exactly one character.

This data structure is called a trie, and it has a lot of cool applications, such as autocomplete.

def has_path(t, target):
    """Return whether there is a path in a Tree where the entries along the path
    spell out a particular target.

    >>> greetings = Tree('h', [Tree('i'),
    ...                        Tree('e', [Tree('l', [Tree('l', [Tree('o')])]),
    ...                                   Tree('y')])])
    >>> print(greetings)
    h
      i
      e
        l
          l
            o
        y
    >>> has_path(greetings, 'h')
    True
    >>> has_path(greetings, 'i')
    False
    >>> has_path(greetings, 'hi')
    True
    >>> has_path(greetings, 'hello')
    True
    >>> has_path(greetings, 'hey')
    True
    >>> has_path(greetings, 'bye')
    False
    >>> has_path(greetings, 'hint')
    False
    """
    assert len(target) > 0, 'no path for empty target.'
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q has_path

Write a function duplicate_link that takes in a linked list lnk and a value. duplicate_link will mutate lnk such that if there is a linked list node that has a first equal to value, that node will be duplicated. Note that you should be mutating the original link list lnk; you will need to create new Links, but you should not be returning a new linked list.

Note: in order to insert a link into a linked list, you need to modify the .rest of certain links. We encourage you to draw out a doctest to visualize!

def duplicate_link(lnk, val):
    """Mutates `lnk` such that if there is a linked list
    node that has a first equal to value, that node will
    be duplicated. Note that you should be mutating the
    original link list.

    >>> x = Link(5, Link(4, Link(3)))
    >>> duplicate_link(x, 5)
    >>> x
    Link(5, Link(5, Link(4, Link(3))))
    >>> y = Link(2, Link(4, Link(6, Link(8))))
    >>> duplicate_link(y, 10)
    >>> y
    Link(2, Link(4, Link(6, Link(8))))
    >>> z = Link(1, Link(2, (Link(2, Link(3)))))
    >>> duplicate_link(z, 2) #ensures that back to back links with val are both duplicated
    >>> z
    Link(1, Link(2, Link(2, Link(2, Link(2, Link(3))))))
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q duplicate_link

Q4: Deep Map

Implement deep_map, which takes a function f and a link. It returns a new linked list with the same structure as link, but with f applied to any element within link or any Link instance contained in link.

The deep_map function should recursively apply fn to each of that Link's elements rather than to that Link itself.

Hint: You may find the built-in isinstance function for checking if something is an instance of an object. For example:

>>> isinstance([1, 2, 3], list)
True
>>> isinstance(Link(1), Link)
True
>>> isinstance(Link(1, Link(2)), list)
False
def deep_map(f, link):
    """Return a Link with the same structure as link but with fn mapped over
    its elements. If an element is an instance of a linked list, recursively
    apply f inside that linked list as well.

    >>> s = Link(1, Link(Link(2, Link(3)), Link(4)))
    >>> print(deep_map(lambda x: x * x, s))
    <1 <4 9> 16>
    >>> print(s) # unchanged
    <1 <2 3> 4>
    >>> print(deep_map(lambda x: 2 * x, Link(s, Link(Link(Link(5))))))
    <<2 <4 6> 8> <<10>>>
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q deep_map

Submit

Make sure to submit this assignment by running:

python3 ok --submit

Optional Questions

Homework assignments will also contain prior exam-level questions for you to take a look at. These questions have no submission component; feel free to attempt them if you'd like a challenge!

  1. Spring 2018 MT2 Q5ab: Trees
  2. Spring 2019 MT2 Q6a: Trie this
  3. Fall 2017 Final Q4a: O! Pascal