# Homework 5

*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.
>>> lst1 = link(1, link(2, link(3, link(4))))
>>> is_sorted(lst1)
True
>>> lst2 = link(1, link(3, link(2, link(4, link(5)))))
>>> is_sorted(lst2)
False
>>> lst3 = link(3, link(3, link(3)))
>>> is_sorted(lst3)
True
"""
"*** YOUR CODE HERE ***"
```

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):
"""Interleave linked lists s0 and s1 to produce a new linked
list.
>>> evens = link(2, link(4, link(6, link(8, empty))))
>>> odds = link(1, link(3, empty))
>>> print_link(interleave(odds, evens))
1 2 3 4 6 8
>>> print_link(interleave(evens, odds))
2 1 4 3 6 8
>>> print_link(interleave(odds, odds))
1 1 3 3
"""
"*** YOUR CODE HERE ***"
```

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 theheight 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
"""
"*** YOUR CODE HERE ***"
```

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
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q sprout_leaves`