Lab 7: Generators, Linked Lists, and Trees

Due by 11:59pm on Friday, October 18.

Starter Files

Download lab07.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the Ok autograder.

Submission

By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded. Check that you have successfully submitted your code on okpy.org.

Required Questions

What Would Python Display?

Q1: WWPD: Linked Lists

Read over the Link class in lab07.py. Make sure you understand the doctests.

Use Ok to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q link -u

Enter Function if you believe the answer is <function ...>, Error if it errors, and Nothing if nothing is displayed.

If you get stuck, try drawing out the box-and-pointer diagram for the linked list on a piece of paper or loading the Link class into the interpreter with python3 -i lab07.py.

>>> from lab07 import *
>>> link = Link(1000)
>>> link.first
______
1000
>>> link.rest is Link.empty
______
True
>>> link = Link(1000, 2000)
______
AssertionError
>>> link = Link(1000, Link())
______
TypeError
>>> from lab07 import *
>>> link = Link(1, Link(2, Link(3)))
>>> link.first
______
1
>>> link.rest.first
______
2
>>> link.rest.rest.rest is Link.empty
______
True
>>> link.first = 9001 >>> link.first
______
9001
>>> link.rest = link.rest.rest >>> link.rest.first
______
3
>>> link = Link(1) >>> link.rest = link >>> link.rest.rest.rest.rest.first
______
1
>>> link = Link(2, Link(3, Link(4))) >>> link2 = Link(1, link) >>> link2.first
______
1
>>> link2.rest.first
______
2

Q2: WWPD: Trees

Use Ok to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q trees-wwpd -u

Enter Function if you believe the answer is <function ...>, Error if it errors, and Nothing if nothing is displayed. Recall that Tree instances will be displayed the same way they are constructed.

>>> from lab07 import *
>>> t = Tree(1, Tree(2))
______
Error
>>> t = Tree(1, [Tree(2)]) >>> t.label
______
1
>>> t.branches[0]
______
Tree(2)
>>> t.branches[0].label
______
2
>>> t.label = t.branches[0].label >>> t
______
Tree(2, [Tree(2)])
>>> t.branches.append(Tree(4, [Tree(8)])) >>> len(t.branches)
______
2
>>> t.branches[0]
______
Tree(2)
>>> t.branches[1]
______
Tree(4, [Tree(8)])

Generators

Iterators also allow us to represent infinite sequences, such as the sequence of natural numbers (1, 2, ...).

class Naturals:
    """
    >>> m = Naturals()
    >>> [next(m) for _ in range(5)]
    [1, 2, 3, 4, 5]
    """
    def __init__(self):
        self.current = 0

    def __iter__(self):
        return self

    def __next__(self):
        self.current += 1
        return self.current

Q3: Scale

Implement the generator function scale(s, k), which yields elements of the given iterable s, scaled by k. As an extra challenge, try writing this function using a yield from statement!

def scale(s, k):
    """Yield elements of the iterable s scaled by a number k.

    >>> s = scale([1, 5, 2], 5)
    >>> type(s)
    <class 'generator'>
    >>> list(s)
    [5, 25, 10]

    >>> m = scale(naturals(), 2)
    >>> [next(m) for _ in range(5)]
    [2, 4, 6, 8, 10]
    """
"*** YOUR CODE HERE ***"
for elem in s: yield elem * k # Alternate solution def scale(s, k): yield from map(lambda x: x*k, s)

Use Ok to test your code:

python3 ok -q scale

Linked Lists

Q4: Link to List

Write a function link_to_list that takes in a linked list and returns the sequence as a Python list. You may assume that the input list is shallow; none of the elements is another linked list.

Try to find both an iterative and recursive solution for this problem!

def link_to_list(link):
    """Takes a linked list 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 ***"
# Recursive solution if link is Link.empty: return [] return [link.first] + link_to_list(link.rest) # Iterative solution def link_to_list(link): result = [] while link is not Link.empty: result.append(link.first) link = link.rest return result # Video Walkthrough: https://youtu.be/hdO9Ry8d5FU?t=25m6s

Use Ok to test your code:

python3 ok -q link_to_list

Trees

Q5: Cumulative Sum

Write a function cumulative_sum that mutates the Tree t so that each node's label becomes the sum of all labels in the subtree rooted at the node.

def cumulative_sum(t):
    """Mutates t so that each node's label becomes the sum of all labels in
    the corresponding subtree rooted at t.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> cumulative_sum(t)
    >>> t
    Tree(16, [Tree(8, [Tree(5)]), Tree(7)])
    """
"*** YOUR CODE HERE ***"
for b in t.branches: cumulative_sum(b) t.label = sum([b.label for b in t.branches]) + t.label

Use Ok to test your code:

python3 ok -q cumulative_sum

Q6: Is BST

Write a function is_bst, which takes a Tree t and returns True if, and only if, t is a valid binary search tree, which means that:

  • Each node has at most two children (a leaf is automatically a valid binary search tree)
  • The children are valid binary search trees
  • For every node, the entries in that node's left child are less than or equal to the label of the node
  • For every node, the entries in that node's right child are greater than the label of the node

Note that, if a node has only one child, that child could be considered either the left or right child. You should take this into consideration.

Hint: It may be helpful to write helper functions bst_min and bst_max that return the minimum and maximum, respectively, of a Tree if it is a valid binary search tree.

def is_bst(t):
    """Returns True if the Tree t has the structure of a valid BST.

    >>> t1 = Tree(6, [Tree(2, [Tree(1), Tree(4)]), Tree(7, [Tree(7), Tree(8)])])
    >>> is_bst(t1)
    True
    >>> t2 = Tree(8, [Tree(2, [Tree(9), Tree(1)]), Tree(3, [Tree(6)]), Tree(5)])
    >>> is_bst(t2)
    False
    >>> t3 = Tree(6, [Tree(2, [Tree(4), Tree(1)]), Tree(7, [Tree(7), Tree(8)])])
    >>> is_bst(t3)
    False
    >>> t4 = Tree(1, [Tree(2, [Tree(3, [Tree(4)])])])
    >>> is_bst(t4)
    True
    >>> t5 = Tree(1, [Tree(0, [Tree(-1, [Tree(-2)])])])
    >>> is_bst(t5)
    True
    >>> t6 = Tree(1, [Tree(4, [Tree(2, [Tree(3)])])])
    >>> is_bst(t6)
    True
    >>> t7 = Tree(2, [Tree(1, [Tree(5)]), Tree(4)])
    >>> is_bst(t7)
    False
    """
"*** YOUR CODE HERE ***"
def bst_min(t): """Returns the min of t, if t has the structure of a valid BST.""" if t.is_leaf(): return t.label return min(t.label, bst_min(t.branches[0])) def bst_max(t): """Returns the max of t, if t has the structure of a valid BST.""" if t.is_leaf(): return t.label return max(t.label, bst_max(t.branches[-1])) if t.is_leaf(): return True if len(t.branches) == 1: c = t.branches[0] return is_bst(c) and (bst_max(c) <= t.label or bst_min(c) > t.label) elif len(t.branches) == 2: c1, c2 = t.branches valid_branches = is_bst(c1) and is_bst(c2) return valid_branches and bst_max(c1) <= t.label and bst_min(c2) > t.label else: return False

Use Ok to test your code:

python3 ok -q is_bst