Homework 10
Due at 11:59:59 pm on Friday, 11/19/2021.

hw10.zip

Linked Lists

A linked list is either an empty linked list (Link.empty) or a first value and the rest of the linked list.

class Link:
    """
    >>> s = Link(1, Link(2, Link(3)))
    >>> s
    Link(1, Link(2, Link(3)))
    """
    empty = ()

    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

    def __repr__(self):
        if self.rest is not Link.empty:
            rest_str = ', ' + repr(self.rest)
        else:
            rest_str = ''
        return 'Link({0}{1})'.format(repr(self.first), rest_str)

To check if a Link is empty, compare it against the class attribute Link.empty. For example, the below function prints out whether or not the link it is handed is empty:

def test_empty(link):
    if link is Link.empty:
        print('This linked list is empty!')
    else:
        print('This linked list is not empty!')

Note: Linked lists are recursive data structures! A linked list contains the first element of the list (first) and a reference to another linked list (rest) which contains the rest of the values in the list.

Question 1: Link to List

Write a function link_to_list that converts a given Link to a Python list.

def link_to_list(link):
    """Takes a Link and returns a Python list with the same elements.

    >>> link = Link(1, Link(2, Link(3, Link(4))))
    >>> link_to_list(link)
    [1, 2, 3, 4]
    >>> link_to_list(Link.empty)
    []
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q link_to_list

Question 2: Every Other

Implement every_other, which takes a linked list s. It mutates s such that all of the odd-indexed elements (using 0-based indexing) are removed from the list. For example:

>>> s = Link('a', Link('b', Link('c', Link('d'))))
>>> every_other(s)
>>> s.first
'a'
>>> s.rest.first
'c'
>>> s.rest.rest is Link.empty
True

If s contains fewer than two elements, s remains unchanged.

Do not return anything! every_other should mutate the original list.

def every_other(s):
    """Mutates a linked list so that all the odd-indiced elements are removed
    (using 0-based indexing).

    >>> s = Link(1, Link(2, Link(3, Link(4))))
    >>> every_other(s)
    >>> s
    Link(1, Link(3))
    >>> odd_length = Link(5, Link(3, Link(1)))
    >>> every_other(odd_length)
    >>> odd_length
    Link(5, Link(1))
    >>> singleton = Link(4)
    >>> every_other(singleton)
    >>> singleton
    Link(4)
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q every_other

Trees

Question 3: Leaves

Write a function leaves that returns a list of all the entries 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 4: Path

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

def path(t, value):
    """
    >>> 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 5: Find Level

Implement find_level, which takes a tree t and an integer level and returns a list of all the entries that have depth level. If no such entries exists, 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