# Homework 5: Trees, Linked Lists hw05.zip

Due by 11:59pm on Thursday, July 28

## 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. Check that you have successfully submitted your code on okpy.org. See Lab 0 for more 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:

Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. There is a homework recovery policy as stated in the syllabus. This homework is out of 2 points.

# Required Questions

## Getting Started Videos

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your berkeley.edu email.

## Code Writing Questions

Implement `add_d_leaves`, a function that takes in a `Tree` instance `t` and a number `v`.

We define the depth of a node in `t` to be the number of edges from the root to that node. The depth of root is therefore 0.

For each node in the tree, you should add `d` leaves to it, where `d` is the depth of the node. Every added leaf should have a label of `v`. If the node at this depth has existing branches, you should add these leaves to the end of that list of branches.

For example, you should be adding 1 leaf with label `v` to each node at depth 1, 2 leaves to each node at depth 2, and so on.

Here is an example of a tree `t`(shown on the left) and the result after `add_d_leaves` is applied with `v` as 5.

Try drawing out the second doctest to visualize how the function is mutating `t3`.

Hint: Use a helper function to keep track of the depth!

``````def add_d_leaves(t, v):
"""Add d leaves containing v to each node at every depth d.

>>> t_one_to_four = Tree(1, [Tree(2), Tree(3, [Tree(4)])])
>>> print(t_one_to_four)
1
2
3
4
>>> print(t_one_to_four)
1
2
5
3
4
5
5
5

>>> t1 = Tree(1, [Tree(3)])
>>> t1
Tree(1, [Tree(3, [Tree(4)])])
>>> t2 = Tree(2, [Tree(5), Tree(6)])
>>> t3 = Tree(3, [t1, Tree(0), t2])
>>> print(t3)
3
1
3
4
0
2
5
6
>>> print(t3)
3
1
3
4
10
10
10
10
10
10
0
10
2
5
10
10
6
10
10
10
"""
``````

Use Ok to test your code:

``python3 ok -q add_d_leaves``

### Q2: Has Path

Write a function `has_path` that takes in a Tree `t` and a string `target`. It returns `True` if there is a path that starts from the root where the entries along the path spell out the `target`, and `False` otherwise. You may assume that every node's `label` is exactly one character.

This data structure is called a trie, and it has a lot of cool applications, such as autocomplete.

``````def has_path(t, target):
"""Return whether there is a path in a Tree where the entries along the path
spell out a particular target.

>>> greetings = Tree('h', [Tree('i'),
...                        Tree('e', [Tree('l', [Tree('l', [Tree('o')])]),
...                                   Tree('y')])])
>>> print(greetings)
h
i
e
l
l
o
y
>>> has_path(greetings, 'h')
True
>>> has_path(greetings, 'i')
False
>>> has_path(greetings, 'hi')
True
>>> has_path(greetings, 'hello')
True
>>> has_path(greetings, 'hey')
True
>>> has_path(greetings, 'bye')
False
>>> has_path(greetings, 'hint')
False
"""
assert len(target) > 0, 'no path for empty target.'
``````

Use Ok to test your code:

``python3 ok -q has_path``

Write a function `duplicate_link` that takes in a linked list `lnk` and a `value`. `duplicate_link` will mutate `lnk` such that if there is a linked list node that has a `first` equal to `value`, that node will be duplicated. Note that you should be mutating the original link list `lnk`; you will need to create new `Link`s, but you should not be returning a new linked list.

Note: in order to insert a link into a linked list, you need to modify the `.rest` of certain links. We encourage you to draw out a doctest to visualize!

``````def duplicate_link(lnk, val):
"""Mutates `lnk` such that if there is a linked list
node that has a first equal to value, that node will
be duplicated. Note that you should be mutating the

>>> x
>>> y
>>> duplicate_link(z, 2) #ensures that back to back links with val are both duplicated
>>> z
"""
``````

Use Ok to test your code:

``python3 ok -q duplicate_link``

### Q4: Deep Map

Implement `deep_map`, which takes a function `f` and a `link`. It returns a new linked list with the same structure as `link`, but with `f` applied to any element within `link` or any `Link` instance contained in `link`.

The `deep_map` function should recursively apply `fn` to each of that `Link`'s elements rather than to that `Link` itself.

Hint: You may find the built-in `isinstance` function for checking if something is an instance of an object. For example:

``````>>> isinstance([1, 2, 3], list)
True
True
False``````
``````def deep_map(f, link):
"""Return a Link with the same structure as link but with fn mapped over
its elements. If an element is an instance of a linked list, recursively
apply f inside that linked list as well.

>>> print(deep_map(lambda x: x * x, s))
<1 <4 9> 16>
>>> print(s) # unchanged
<1 <2 3> 4>
<<2 <4 6> 8> <<10>>>
"""
``````

Use Ok to test your code:

``python3 ok -q deep_map``

## Submit

Make sure to submit this assignment by running:

``python3 ok --submit``

# Optional Questions

Homework assignments will also contain prior exam-level questions for you to take a look at. These questions have no submission component; feel free to attempt them if you'd like a challenge!

1. Spring 2018 MT2 Q5ab: Trees
2. Spring 2019 MT2 Q6a: Trie this
3. Fall 2017 Final Q4a: O! Pascal