Due by 11:59pm on Saturday, 7/18

## 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. See Lab 1 for 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:

## Mid-semester Survey

Please fill out the mid-semester survey. We appreciate any feedback that you have for us; we want to know what works for you in this class and what doesn't.

## Required questions

### Question 1: is_sorted

Implement the `is_sorted(lst)` function, which returns `True` if the linked list `lst` is sorted in increasing from left to right. If two adjacent elements are equal, the linked list is still considered sorted.

``````def is_sorted(lst):
"""Returns True if the linked list is sorted.

>>> is_sorted(lst1)
True
>>> is_sorted(lst2)
False
>>> is_sorted(lst3)
True
"""

Use OK to test your code:

``python3 ok -q is_sorted``

### Question 2: Interleave

Write `interleave(s0, s1)`, which takes two linked lists and produces a new linked list with elements of `s0` and `s1` interleaved. In other words, the resulting list should have the first element of the `s0`, the first element of `s1`, the second element of `s0`, the second element of `s1`, and so on.

If the two lists are not the same length, then the leftover elements of the longer list should still appear at the end.

``````def interleave(s0, s1):
list.

1 2 3 4 6 8
2 1 4 3 6 8
1 1 3 3
"""

Use OK to test your code:

``python3 ok -q interleave``

### Question 3: Height

Define the function `height`, which takes in a tree as an argument and returns the number of branches it takes start at the root node and reach the leaf that is farthest away from the root.

Note: given the definition of the height of a tree, if `height` is given a leaf, what should it return?

``````def height(t):
"""Return the depth of the deepest node in the tree.

>>> height(tree(1))
0
>>> height(tree(1, [tree(2), tree(3)]))
1
>>> print_tree(numbers)
1
2
3
4
5
6
7
>>> height(numbers)
2
"""

Use OK to test your code:

``python3 ok -q height``

### Question 4: Sprout leaves

Define a function `sprout_leaves` that, given a tree, `t`, and a list of values, `vals`, and produces a tree with every leaf having new children that contain each of the items in `vals`. Do not add new children to non-leaf nodes.

``````def sprout_leaves(t, vals):
"""Sprout new leaves containing the data in vals at each leaf in
the original tree t and return the resulting tree.

>>> t1 = tree(1, [tree(2), tree(3)])
>>> print_tree(t1)
1
2
3
>>> new1 = sprout_leaves(t1, [4, 5])
>>> print_tree(new1)
1
2
4
5
3
4
5

>>> t2 = tree(1, [tree(2, [tree(3)])])
>>> print_tree(t2)
1
2
3
>>> new2 = sprout_leaves(t2, [6, 1, 2])
>>> print_tree(new2)
1
2
3
6
1
2
"""
``python3 ok -q sprout_leaves``