# 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`