Homework 9
Due at 11:59:59 pm on Sunday, 4/12/2020.
Instructions
Download hw09.zip. Inside the archive, you will find starter files for the questions in this homework, 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 this article for more instructions on okpy and submitting assignments.
Readings: This homework relies on following references:
Trees
Question 1: Search
Write a function search that returns the Tree, whose entry is the given value if it exists and None if it does not. You can assume all entries are unique.
def search(t, value):
"""Searches for and returns the Tree whose entry is equal to value if
it exists and None if it does not. Assume unique entries.
>>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
>>> search(t, 10)
>>> search(t, 5)
Tree(5)
>>> search(t, 1)
Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
"""
"*** YOUR CODE HERE ***"Use OK to test your code:
python3 ok -q searchQuestion 2: Tree Map
Define the function tree_map, which takes in a tree and a
one-argument function as arguments and returns a new tree which is the
result of mapping the function over the entries of the input tree.
def tree_map(fn, t):
"""Maps the function fn over the entries of t and returns the
result in a new tree.
>>> numbers = Tree(1,
... [Tree(2,
... [Tree(3),
... Tree(4)]),
... Tree(5,
... [Tree(6,
... [Tree(7)]),
... Tree(8)])])
>>> print(tree_map(lambda x: 2**x, numbers))
2
4
8
16
32
64
128
256
>>> print(numbers)
1
2
3
4
5
6
7
8
"""
"*** YOUR CODE HERE ***"Use OK to test your code:
python3 ok -q tree_mapQuestion 3: Add Leaves
Implement add_d_leaves, a function that takes in a Tree instance t and
mutates it so that at each depth d in the tree, d leaves with labels v
are added to each node at that depth. For example, we want to add 1 leaf with
v in it to each node at depth 1, 2 leaves to each node at depth 2, and so on.
Recall that the depth of a node is the number of edges from that node to the root, so the depth of the root is 0. The leaves should be added to the end of the list of branches.
def add_d_leaves(t, v):
"""Add d leaves containing v to each node at every depth d.
>>> t1 = Tree(1, [Tree(3)])
>>> add_d_leaves(t1, 4)
>>> t1
Tree(1, [Tree(3, [Tree(4)])])
>>> t2 = Tree(2, [Tree(5), Tree(6)])
>>> t3 = Tree(3, [t1, Tree(0), t2])
>>> add_d_leaves(t3, 10)
>>> print(t3)
3
1
3
4
10
10
10
10
10
10
0
10
2
5
10
10
6
10
10
10
"""
def add_leaves(t, d):
"*** YOUR CODE HERE ***"
add_leaves(t, 0)Use OK to test your code:
python3 ok -q add_d_leavesQuestion 4: Long Paths
Implement long_paths, which returns a list of all paths in a tree with
length at least n. A path in a tree is a linked list of node values that
starts with the root and ends at a leaf. Each subsequent element must be from a
branch of the previous value's node. The length of a path is the number of
edges in the path (i.e. one less than the number of nodes in the path).
Paths are listed in branch order i.e. from left to right.
def long_paths(tree, n):
"""Return a list all paths in tree with length at least n.
>>> t = Tree(3, [Tree(4), Tree(4), Tree(5)])
>>> left = Tree(1, [Tree(2), t])
>>> mid = Tree(6, [Tree(7, [Tree(8)]), Tree(9)])
>>> right = Tree(11, [Tree(12)])
>>> whole = Tree(0, [left, Tree(13), mid, right])
>>> for path in long_paths(whole, 2):
... print_link(path)
...
<0 1 2>
<0 1 3 4>
<0 1 3 4>
<0 1 3 5>
<0 6 7 8>
<0 6 9>
<0 11 12>
>>> for path in long_paths(whole, 3):
... print_link(path)
...
<0 1 3 4>
<0 1 3 4>
<0 1 3 5>
<0 6 7 8>
>>> long_paths(whole, 4)
[]
"""
paths = []
"*** YOUR CODE HERE ***"
return pathsUse OK to test your code:
python3 ok -q long_pathsOptional Question
Question 5: Partial Tree
The sequence_to_tree function takes a sorted linked list and converts it into
a balanced Tree in which every sub-tree has at most two branches. For every
subtree with 2 branches, all nodes in the left branch are smaller than the root
of the subtree and all nodes in the right branch are larger.
A Tree is balanced if
- It is a leaf, or
- It has exactly one branch that is a leaf, or
- It has two branches and the number of nodes in its first branch differs from the number of nodes in its second branch by at most 1, and both branches are also balanced.
In order to write sequence_to_tree, implement partial_tree(s, n),
which converts the first n elements of the sorted linked list s into a
balanced Tree. The return value is a two-element tuple: the resulting
balanced tree; and the rest of the linked list.
Hint: This function requires two recursive calls. The first call builds a left branch out of the first
left_sizeelements of s; Then, the next element is used as the entry of the returned tree. Finally, the second recursive call builds the right branch out of the nextright_sizeelements. In total,(left_size + 1 + right_size) = n, where 1 is for the entry:
def partial_tree(s, n):
"""Return a balanced tree of the first n elements of Link s, along with
the rest of s.
Examples of balanced trees:
Tree(1) # leaf
Tree(1, [Tree(2)]) # one branch is a leaf
Tree(1, [Tree(2), Tree(3)]) # two branches with one node each
Examples of unbalanced trees:
Tree(1, [Tree(2, [Tree(3)])]) # one branch not a leaf
Tree(1, [Tree(2), # Mismatch: branch with 1 node
Tree(3, [Tree(4, [Tree(5)])])]) # vs branch with 3 nodes
>>> s = Link(1, Link(2, Link(3, Link(4, Link(5)))))
>>> partial_tree(s, 3)
(Tree(2, [Tree(1), Tree(3)]), Link(4, Link(5)))
>>> t = Link(-2, Link(-1, Link(0, s)))
>>> partial_tree(t, 7)[0]
Tree(1, [Tree(-1, [Tree(-2), Tree(0)]), Tree(3, [Tree(2), Tree(4)])])
>>> partial_tree(t, 7)[1]
Link(5)
"""
if n == 1:
return (Tree(s.first), s.rest)
elif n == 2:
return (Tree(s.first, [Tree(s.rest.first)]), s.rest.rest)
else:
left_size = (n-1)//2
right_size = n - left_size - 1
"*** YOUR CODE HERE ***"
def sequence_to_tree(s):
"""Return a balanced tree containing the elements of sorted Link s.
Note: this implementation is complete, but the definition of partial_tree
above is not complete.
>>> sequence_to_tree(Link(1, Link(2, Link(3))))
Tree(2, [Tree(1), Tree(3)])
>>> elements = Link(1, Link(2, Link(3, Link(4, Link(5, Link(6, Link(7)))))))
>>> sequence_to_tree(elements)
Tree(4, [Tree(2, [Tree(1), Tree(3)]), Tree(6, [Tree(5), Tree(7)])])
"""
return partial_tree(s, len(s))[0]Use OK to test your code:
python3 ok -q partial_tree