[SOLVED] C algorithm Q2 Contaminated nodes in a tree (25 marks)

Q2 Contaminated nodes in a tree (25 marks)

You are given a tree $T$ with a set of nodes $V$. The tree $T$ can have arbitrary degree, i.e. nodes can have arbitrarily many children. A subset of the nodes of $V$, called $C$, is contaminated. The other nodes, called $P$, contain a population. Hence every node either belongs to the set $C$ or $P$. A population node in $P$ is safe if it is not connected to a contaminated node in $C$, i.e. there exists no path between the population node and any contaminated node.
Your task is to find the minimum number of edges of the tree $T$ that must be cut (i.e. deleted) such that all population nodes are safe.
Examples are provided in the unit tests.

Q2.1 (5 marks)
Describe an algorithm to solve this problem. An unclear or unspecific description will get 0 marks. There is no constraint on the type of algorthm to use, but more efficient algorithms get more marks.

(write your answer here).

Q2.2 (5 marks)
What is the worst-case runtime complexity of your algorithm? Explain.

(write your answer here).

Q2.3 (15 marks)
Implement below the algorithm you have described above, with the complexity to match.
For this question we provide a class Node to store the problem data. You can expand this class but you cannot change the existing variables. In particular it may prove useful to write an __str__ method to help with potential debugging. The method __str__ itself will not be marked.
In[0]:
class Node:
def __init__(self, contaminated=False):
self.children = []
self.contaminated = contaminated

def addChild(self, node):
self.children.append(node)

#TODO extend this class here if needed

Implement your algorithm below:
In[0]:
def mincosttosave(tree):
Returns the minimum number of edges that must be cut to
save all the population nodes of the tree.
@param tree The root Node
#TODO
pass

We provide unit tests below. Your implementation must pass all tests to get full marks. For reference, the solution code runs in less than .1 second. If your code requires a significant longer time to run, then it may be bugged, or your algorithm may not be very efficient.
In[0]:
import unittest

class TestSaveTree(unittest.TestCase):
def setUp(self):
pass

def checkcost(self, tree, val):
msg = It should cost exactly {} to save all nodes in the tree:
{}..format(val, tree)
self.assertEqual(val, mincosttosave(tree), msg=msg)

def testSingle(self):
self.checkcost(Node(False), 0)

def testTwo(self):
#A single edge with no C
for top in [False, True]:
for left in [False, True]:
root = Node(top)
child = Node(left)
root.addChild(child)
self.checkcost(root, int(top is not left))

def testTriangle(self):
#a root with two children
for top in [False, True]:
for left in [False, True]:
for right in [False, True]:
root = Node(top)
leftchild = Node(left)
rightchild = Node(right)
root.addChild(leftchild)
root.addChild(rightchild)
self.checkcost(root, int(top is not left)+int(top is not right))

def buildtree(self, nodelist, degree=2):
nodes = [Node(c) for c in nodelist]
for i in range(1,len(nodes)):
nodes[(i-1)//degree].addChild(nodes[i])
return nodes[0]

def testSmallDeg2(self):
tests = []
degree = 2
tests.append(([True, True, True, False], 1))
tests.append(([True, False, True, False], 1))
tests.append(([False, False, False, False], 0))
tests.append(([True, False, False, False], 2))
tests.append(([True, True, False, True, True, True, False, True], 2))
tests.append(([False, False, True, False, True, True, False, True], 4))
tests.append(([True, True, True, False, False, False, False, True], 5))
tests.append(([False, False, True, True, False, False, True, True], 3))
tests.append(([True, False, True, False, False, True, True, False], 1))
for test in tests:
tree = self.buildtree(test[0], degree)
self.checkcost(tree, test[1])

def testSmallDeg3(self):
tests = []
degree = 3
tests.append(([True, True, False, True, False, False, True, False], 3))
tests.append(([False, False, True, False, False, False, True, False], 3))
tests.append(([True, True, False, True, False, True, True, False], 2))
tests.append(([False, True, False, True, False, False, True, False], 4))
tests.append(([False, False, True, False, True, True, True, False], 5))
tests.append(([True, False, False, False, True, False, True, True], 6))
for test in tests:
tree = self.buildtree(test[0], degree)
self.checkcost(tree, test[1])

def testSmallDeg5(self):
tests = []
degree = 5
tests.append(([True, True, False, True, False, True, False, True, True, False, False, True, True, True, False, True, False, True, True, False, True, True, True, True, True, True, True, False, True, True, False, False, True, False, False, False, False, True, True, False, False, False, False, False, True, True, True, True, True, True], 29))
tests.append(([True, True, True, False, False, True, True, False, True, True, False, False, True, True, False, False, False, False, True, False, False, False, True, True, True, False, True, True, True, False, False, False, True, True, False, True, True, False, True, False, False, False, True, False, False, True, False, False, False, False], 24))
tests.append(([True, True, False, False, False, False, True, False, False, False, False, True, True, True, False, True, True, False, False, False, True, True, False, True, False, True, True, True, False, True, False, True, True, False, False, True, True, False, True, False, True, False, True, True, False, True, False, False, True, True], 30))
tests.append(([True, False, False, True, False, False, True, True, False, False, True, False, False, False, False, True, True, True, True, True, False, False, True, False, True, True, True, True, False, False, False, False, True, False, False, False, True, False, False, False, False, False, True, True, True, True, False, False, True, False], 27))
tests.append(([False, True, False, True, True, False, False, True, False, True, True, True, False, False, False, False, True, True, False, False, True, False, True, False, False, True, True, False, True, True, True, False, False, False, True, True, False, False, False, True, False, True, True, False, False, True, False, True, True, False], 26))
tests.append(([True, False, False, False, False, False, True, False, True, True, True, True, True, True, True, False, True, False, True, True, True, False, False, False, False, False, False, True, False, True, True, True, True, True, False, True, False, True, False, True, False, False, False, False, True, True, False, True, False, True], 28))
tests.append(([False, True, True, False, True, False, True, True, False, False, False, True, True, False, True, True, False, True, False, True, False, True, False, True, True, False, True, False, True, True, True, False, True, True, False, False, False, False, True, False, False, False, True, False, False, True, True, False, True, True], 27))
tests.append(([False, True, False, False, False, False, True, True, False, True, True, False, False, True, False, True, True, False, True, False, True, True, False, True, False, False, True, False, False, False, True, True, False, True, True, True, False, False, True, True, False, True, True, True, False, False, True, True, False, False], 20))
tests.append(([True, True, True, True, False, False, False, True, False, True, True, False, True, False, True, False, True, True, False, False, True, True, False, True, True, True, False, False, False, False, True, False, True, True, False, True, False, True, True, False, False, False, False, True, True, True, False, False, True, False], 26))
tests.append(([False, False, False, True, True, True, False, True, False, True, False, True, True, False, False, True, False, False, False, False, False, False, False, True, False, False, True, False, False, True, True, False, False, False, False, False, False, False, True, True, False, False, True, False, True, False, True, True, False, False], 26))
for test in tests:
tree = self.buildtree(test[0], degree)
self.checkcost(tree, test[1])

def testBigDeg2(self):
tests = []
degree = 2
tests.append(([True, False, False, False, False, True, False, True, False, True, False, True, False, False, True, False, False, True, False, False, False, False, True, False, False, True, False, True, False, False, True, False, True, True, False, True, True, True, False, True, True, True, True, False, True, False, False, False, True, True, True, True, True, False, True, True, True, True, False, False, False, False, False, False, False, True, False, True, True, False, False, False, True, True, False, False, False, False, False, True, False, True, False, False, False, True, True, True, False, True, True, False, True, True, False, False, True, False, True, True, False, False, False, True, True, False, True, False, True, False, True, True, True, True, True, True, False, True, True, True, True, True, True, True, True, False, False, True, True, False, False, False, True, False, True, True, False, False, False, True, False, False, False, False, False, True, False, False, True, True, True, True, False, False, False, False, False, True, False, True, False, False, False, True, True, True, True, True, False, False, False, False, False, True, False, False, True, False, True, False, False, True, True, True, False, True, True, False, False, True, True, True, True, True, False, True, True, True, True, False], 100))
tests.append(([False, True, True, True, True, True, False, True, True, True, False, False, False, True, True, True, False, False, True, True, True, True, False, False, True, False, True, True, True, False, True, True, False, False, False, False, False, False, True, True, True, True, True, True, True, False, False, False, False, True, True, False, False, True, False, False, True, False, True, False, False, True, False, False, False, False, False, True, True, False, False, False, True, True, False, True, False, False, True, True, True, False, False, False, False, False, True, True, False, True, True, False, True, True, False, False, False, False, True, False, True, True, False, True, True, True, False, False, True, False, True, False, False, True, True, False, True, False, False, True, True, True, False, True, True, True, False, False, False, False, False, True, False, False, False, True, True, False, False, False, True, False, True, True, True, False, True, False, False, True, False, True, True, False, False, False, False, False, True, False, False, True, False, False, True, True, True, True, False, False, False, False, False, False, True, True, True, False, True, True, False, True, True, False, True, False, False, True, False, True, False, True, True, True, True, True, True, False, False, False], 86))
tests.append(([False, False, False, True, False, True, False, False, False, True, False, True, True, False, False, True, False, True, True, True, True, False, False, False, True, True, False, True, False, False, True, False, True, True, False, True, True, True, False, False, False, True, True, True, False, False, True, True, True, False, True, True, False, False, True, False, False, True, True, True, False, False, False, False, False, False, True, False, True, True, True, False, False, True, False, False, False, True, True, True, True, False, False, True, False, False, True, True, False, True, True, False, True, True, True, True, False, False, False, False, True, True, False, True, False, False, False, False, True, False, False, False, False, True, False, False, False, True, False, True, True, False, True, False, False, True, True, True, True, False, False, False, True, False, True, True, True, True, False, True, True, False, True, True, True, True, True, True, False, False, True, False, False, True, True, False, True, False, True, False, False, True, True, True, True, True, True, True, True, False, True, True, True, True, True, False, True, False, True, False, False, False, True, False, True, True, False, True, False, True, True, False, False, False, False, False, True, False, True, True], 106))
tests.append(([True, False, True, False, False, True, False, False, False, True, False, True, True, True, False, False, False, False, False, True, True, True, True, True, False, True, True, True, False, True, False, False, True, True, False, False, False, False, False, False, True, True, False, False, False, True, False, True, True, True, False, False, True, False, False, False, False, True, False, True, False, True, False, True, True, True, True, True, True, False, True, False, False, True, False, True, False, True, False, True, True, True, True, False, True, True, False, False, False, True, True, True, True, False, False, True, False, True, True, True, False, False, False, False, True, False, True, True, True, True, False, False, True, False, False, True, False, True, True, False, False, True, False, False, False, True, False, False, True, True, False, True, True, True, False, False, True, True, True, False, True, True, False, True, True, True, True, False, False, False, False, False, True, False, False, False, False, True, False, True, False, False, True, False, False, True, True, False, True, False, False, True, True, True, False, False, False, False, True, False, True, False, False, False, True, False, False, True, False, False, False, True, False, False, True, False, True, True, False, False], 91))
tests.append(([True, True, True, True, True, False, True, False, False, True, False, False, False, True, True, True, False, True, False, False, False, True, True, True, True, True, True, True, True, True, False, True, True, True, True, True, False, True, True, True, False, False, True, True, True, True, False, False, False, False, False, False, True, False, False, True, False, False, True, True, False, False, False, True, True, True, True, False, True, False, False, False, False, True, False, True, False, False, True, True, True, False, False, True, True, False, True, True, False, False, False, True, False, False, False, False, True, False, True, True, True, False, False, True, False, False, True, True, False, False, True, False, True, True, False, True, True, True, True, False, False, False, False, False, True, False, False, True, False, True, True, True, True, True, True, True, True, True, False, False, False, True, False, True, True, False, False, False, True, True, False, False, False, True, False, False, True, False, False, True, True, False, True, False, False, False, False, True, False, True, False, False, False, True, False, True, False, False, True, True, False, False, False, True, False, False, True, False, True, False, False, True, True, False, False, True, True, True, True, True], 94))
tests.append(([False, True, False, True, False, True, False, False, False, False, True, True, True, False, False, True, True, True, True, True, True, True, True, True, False, True, True, False, False, False, True, False, True, True, False, False, True, False, False, True, True, False, False, False, True, False, False, True, False, True, True, True, False, True, False, False, True, True, True, False, False, False, False, False, False, True, True, False, True, True, False, False, True, True, False, True, False, True, True, True, False, True, True, False, True, True, False, False, False, False, True, False, True, True, False, False, True, False, True, False, False, True, False, False, True, True, True, True, True, True, True, False, False, False, False, False, False, False, False, False, False, True, True, True, True, True, False, False, True, True, False, False, True, False, True, False, False, False, False, False, False, True, False, True, False, True, True, True, True, True, True, False, False, False, False, True, True, False, True, True, True, True, True, False, False, True, True, False, True, True, False, True, True, False, True, False, True, True, False, True, True, True, False, True, False, True, False, False, True, False, False, True, False, True, False, True, False, True, False, True], 103))
tests.append(([True, False, False, True, False, True, True, False, False, True, False, False, True, False, True, False, True, False, True, False, False, True, False, True, False, True, True, True, True, True, True, False, False, True, True, False, True, False, True, True, True, True, False, True, True, True, False, False, True, True, True, False, True, False, True, False, True, True, False, False, False, True, True, False, True, False, True, True, False, True, True, False, True, True, False, True, True, True, True, False, False, False, True, False, True, True, True, False, True, True, True, True, True, False, True, False, False, True, False, True, False, True, True, True, False, False, True, False, False, True, False, True, True, True, True, True, True, False, False, False, False, False, True, False, False, True, True, True, True, True, False, False, True, True, False, True, False, False, False, True, False, False, True, True, True, False, True, False, True, True, False, True, True, True, True, False, True, True, True, True, False, True, False, True, True, True, False, True, False, True, True, False, True, True, False, True, False, False, False, True, False, True, False, True, False, False, False, False, True, True, True, True, False, True, True, True, False, True, False, False], 95))
tests.append(([True, True, False, True, False, True, True, True, True, False, False, False, False, False, True, True, True, False, False, True, False, True, True, False, False, True, False, True, False, True, True, False, True, False, False, True, True, True, False, True, False, True, False, True, True, True, True, False, False, True, True, False, True, True, False, False, True, False, True, False, True, True, False, False, False, True, False, True, False, False, False, True, True, False, True, False, False, False, True, True, True, True, False, False, True, False, True, True, True, False, False, True, False, True, True, False, False, True, True, False, False, True, False, False, False, False, False, True, False, False, False, True, True, False, False, False, False, False, True, False, False, True, False, True, False, False, True, False, True, True, True, True, True, False, True, True, False, True, False, True, True, True, True, True, True, True, True, True, False, False, True, True, False, False, False, True, True, True, False, False, True, True, True, True, True, False, False, False, True, False, True, False, True, True, False, True, False, False, False, True, False, False, False, True, True, True, False, False, True, True, True, True, False, False, False, False, True, False, False, True], 90))
tests.append(([False, False, True, False, False, True, False, False, True, True, False, True, True, True, False, False, False, False, True, False, True, True, True, True, False, True, True, True, True, True, False, True, False, True, True, False, False, False, True, False, True, True, False, True, False, False, True, False, True, False, False, True, True, True, False, False, True, True, False, True, False, False, True, True, True, True, False, False, False, False, True, True, True, False, False, False, True, True, True, True, False, True, False, False, True, True, True, True, True, True, True, False, False, False, True, True, False, True, False, False, False, True, False, False, False, True, True, False, True, False, False, False, True, False, True, False, False, False, False, True, True, True, False, False, True, False, False, True, True, False, True, True, True, True, False, True, False, True, True, False, True, True, True, True, True, False, False, False, False, False, True, False, True, False, True, True, True, True, True, False, True, True, True, True, False, False, False, False, True, False, True, True, False, True, True, True, False, True, False, True, False, False, False, False, False, True, False, True, True, False, False, True, False, False, True, False, False, True, True, True], 89))
tests.append(([False, True, True, False, True, False, True, True, True, True, False, True, False, False, False, True, False, True, True, True, False, True, True, True, True, False, True, False, False, False, False, True, False, True, True, False, True, True, False, False, False, True, True, True, False, False, False, False, True, True, True, False, True, True, False, False, True, False, False, False, False, True, True, True, True, True, False, False, False, False, True, True, False, False, True, False, True, False, False, True, False, True, False, True, True, False, True, True, True, True, True, True, False, False, True, False, True, False, False, True, True, True, True, True, True, True, True, False, True, False, True, False, False, True, False, True, True, True, False, True, True, False, False, True, True, True, True, False, True, True, True, False, True, True, True, True, True, False, True, False, False, False, True, False, True, False, True, True, True, True, True, False, True, True, True, False, False, False, True, True, True, False, False, False, True, False, True, False, False, True, True, False, False, False, True, True, False, False, False, True, False, True, True, True, False, False, True, True, True, True, True, True, False, False, True, True, True, False, False, True], 91))
for test in tests:
tree = self.buildtree(test[0], degree)
self.checkcost(tree, test[1])

def testBigDeg5(self):
tests = []
degree = 5
tests.append(([True, False, False, False, True, True, True, False, True, False, False, True, False, False, False, True, True, False, True, True, False, False, False, True, False, False, False, False, False, True, True, False, False, False, True, False, False, True, False, True, True, True, False, True, True, False, False, True, True, True, True, True, True, True, True, False, True, False, False, False, True, True, False, False, False, True, True, False, False, False, True, True, True, False, True, True, False, False, True, True, True, False, True, False, True, False, True, True, True, False, True, True, True, True, True, False, True, True, False, False, True, True, False, False, False, True, False, True, False, False, False, False, True, False, False, True, False, False, False, True, False, True, False, True, True, True, True, False, True, False, False, False, False, False, False, True, True, True, False, True, False, False, False, True, False, False, False, False, True, False, True, False, True, True, False, False, True, False, False, False, True, False, False, False, True, True, False, False, True, True, True, True, True, True, True, True, True, False, True, True, False, False, True, False, True, True, False, True, True, False, True, False, True, False, False, False, False, False, False, True], 102))
tests.append(([True, False, False, True, True, False, False, True, False, True, False, True, True, True, False, False, False, False, False, False, False, True, False, True, True, True, True, True, False, True, True, False, False, True, False, True, False, True, False, False, True, True, True, False, False, False, False, False, True, True, True, True, True, False, False, False, True, True, False, False, True, True, False, True, True, False, False, False, True, False, True, True, False, False, False, False, True, True, False, True, True, True, True, True, True, True, False, True, False, True, True, True, True, True, True, False, True, True, False, True, False, False, True, True, True, False, True, False, False, True, False, True, True, False, False, True, True, False, False, True, False, True, False, True, True, False, True, True, True, True, False, False, True, False, False, True, True, True, False, True, True, True, False, True, False, False, False, False, False, False, False, True, True, True, True, False, False, True, False, False, False, False, True, False, True, True, False, True, False, False, True, False, True, True, True, True, False, True, False, True, True, True, False, False, True, True, False, False, True, False, True, False, False, True, False, True, True, True, False, False], 106))
tests.append(([False, False, False, False, False, False, False, True, True, True, False, False, True, True, True, True, False, True, False, False, False, True, True, False, True, True, False, False, True, False, False, False, False, True, True, False, False, True, False, False, True, True, False, False, False, False, False, False, True, False, True, True, True, False, False, False, False, False, True, False, True, True, False, False, True, False, True, True, False, False, True, True, True, False, True, False, False, False, True, True, False, False, True, True, False, True, False, False, True, False, True, False, True, False, False, True, True, True, False, True, True, True, False, False, False, True, False, True, False, True, False, True, False, False, True, False, True, False, True, False, True, True, True, True, False, True, False, False, True, True, False, False, True, True, True, True, False, False, True, False, False, False, True, False, True, True, True, False, True, False, True, True, True, True, False, False, False, True, True, True, False, True, False, False, False, True, True, True, True, False, False, True, True, False, False, True, False, True, True, True, False, True, True, True, False, True, True, True, True, False, True, True, True, True, False, True, False, False, False, True], 101))
tests.append(([True, False, False, True, True, True, True, True, True, False, True, True, True, True, False, False, False, False, False, True, False, True, False, True, True, True, False, True, True, True, True, False, True, False, False, False, True, False, True, False, False, False, True, False, False, False, True, True, False, False, False, False, False, False, False, False, False, False, True, True, False, False, True, True, True, True, False, True, False, True, False, True, False, False, False, True, False, False, True, False, False, True, True, True, False, True, True, False, False, False, True, False, False, False, False, True, True, True, True, False, True, True, False, True, False, True, True, True, False, False, False, False, False, False, False, True, True, False, True, False, True, True, True, False, False, True, False, True, True, False, True, True, False, False, True, False, False, False, True, False, False, True, False, False, False, False, False, True, True, True, False, False, True, False, True, True, False, False, True, True, False, True, True, False, True, False, False, True, False, False, True, True, False, True, True, True, True, True, False, True, True, False, True, False, False, False, False, True, True, False, True, True, False, False, False, True, False, True, False, False], 103))
tests.append(([True, True, False, True, False, True, True, False, False, False, True, False, True, True, True, False, True, False, False, False, False, False, False, True, True, True, False, True, True, True, False, True, False, True, False, True, True, False, True, True, True, False, True, True, False, True, True, False, False, True, True, True, True, False, False, False, True, False, False, True, True, True, False, True, True, True, False, False, False, True, True, False, False, True, False, False, True, False, False, False, True, False, True, True, False, True, False, True, False, False, True, True, True, False, True, False, True, True, False, False, False, True, False, False, True, False, False, True, True, True, True, False, False, False, False, True, False, False, False, False, False, True, False, False, False, False, False, True, True, True, False, True, False, True, False, False, False, False, False, True, True, False, True, False, True, True, True, False, False, False, False, True, False, True, True, False, False, False, True, False, False, False, False, True, False, True, True, False, True, True, False, False, True, False, False, True, True, False, True, True, False, True, True, False, False, False, False, True, True, False, True, False, False, False, False, True, False, False, False, True], 111))
tests.append(([False, False, False, False, True, True, True, True, False, False, True, False, True, False, False, True, True, True, False, False, True, True, False, False, True, True, True, True, False, True, True, False, False, False, False, True, False, True, True, True, True, True, True, False, True, True, False, False, True, True, True, False, False, False, False, True, False, True, False, False, True, True, False, False, True, True, False, True, False, False, True, False, True, True, True, True, True, False, True, False, False, True, False, False, True, True, False, False, True, True, False, True, True, True, True, True, True, True, True, True, False, True, True, False, False, False, False, False, False, True, False, False, True, True, False, True, False, False, False, False, True, True, True, False, True, False, True, True, True, False, False, False, True, True, False, False, True, True, True, True, False, True, False, True, False, True, False, False, False, False, True, False, True, True, True, False, False, False, False, True, False, False, False, True, False, True, True, False, False, False, True, True, True, False, False, False, True, False, True, False, True, False, False, True, False, False, False, False, False, True, True, True, True, True, True, False, False, False, True, True], 100))
tests.append(([False, True, False, False, True, False, False, True, False, True, True, True, True, True, True, True, False, True, True, True, True, True, True, True, True, False, False, False, False, False, True, False, True, True, False, False, True, True, True, False, False, False, True, False, True, True, True, True, True, True, True, False, True, True, True, True, True, False, True, False, False, True, False, True, True, True, False, True, True, False, True, True, True, True, False, True, False, True, True, True, True, True, True, True, True, False, False, False, True, False, False, True, True, True, True, False, True, True, False, True, True, False, True, False, False, False, False, False, True, True, True, False, True, True, False, True, False, True, False, False, True, False, True, False, True, False, True, True, True, False, False, False, True, True, False, False, False, True, True, True, True, True, True, False, False, True, True, False, False, True, True, False, False, False, False, False, False, True, True, False, False, False, True, True, False, False, True, True, False, True, False, False, False, True, True, False, False, True, True, True, False, True, True, True, True, True, False, False, False, False, True, True, False, True, True, False, False, True, True, True], 96))
tests.append(([True, False, True, True, False, True, False, False, True, False, False, True, False, False, False, False, False, False, False, True, True, True, False, True, True, True, False, False, False, True, False, True, False, False, True, True, False, True, False, False, False, True, False, True, True, True, False, True, False, True, False, False, False, False, True, False, False, False, False, True, True, True, True, False, True, False, False, False, True, False, False, True, False, True, False, False, False, True, False, True, False, False, False, False, False, False, False, True, False, False, False, True, True, True, True, False, True, False, True, False, True, True, True, True, False, False, False, True, False, True, True, False, False, True, False, True, True, False, False, True, True, True, False, False, False, False, True, False, True, True, False, True, True, False, True, False, False, True, False, False, False, True, True, False, False, False, True, True, False, True, False, True, False, False, False, False, False, False, True, True, False, True, True, False, False, True, True, False, True, False, True, True, False, False, True, True, False, True, False, True, True, True, False, True, False, True, False, True, True, False, True, True, True, True, False, True, True, True, False, True], 92))
tests.append(([True, False, False, True, False, False, True, True, False, False, False, False, False, False, False, False, False, False, True, True, True, True, True, True, False, False, False, True, False, True, False, False, False, False, True, False, False, True, True, False, False, False, True, False, False, True, True, True, False, True, False, False, True, True, False, True, False, False, True, False, False, False, True, True, False, False, False, True, True, True, True, True, False, True, False, True, True, True, True, True, False, False, True, False, False, False, True, True, True, True, False, False, True, True, True, True, True, True, True, True, True, False, False, True, False, False, True, True, True, False, True, True, True, False, True, True, False, False, False, True, False, True, False, False, True, False, False, True, False, True, False, True, False, True, False, False, False, True, False, True, False, False, True, False, True, True, False, True, False, False, False, True, False, True, False, False, True, False, True, False, True, False, False, False, False, False, False, True, True, False, False, False, True, False, True, True, True, True, False, True, True, True, False, False, True, True, True, False, True, True, True, True, True, True, True, True, False, False, True, False], 92))
tests.append(([True, True, False, True, False, True, True, True, True, True, False, False, False, True, False, True, True, False, False, False, False, True, False, False, True, False, True, False, False, False, False, False, True, True, False, False, False, False, False, True, True, False, True, False, True, True, True, False, False, False, True, True, True, False, False, False, True, True, True, False, True, False, True, True, True, True, True, False, True, True, False, True, False, True, True, True, False, False, False, True, True, True, False, True, True, True, True, False, True, True, True, True, False, True, True, True, False, False, False, False, True, False, False, True, False, False, True, True, True, False, True, False, True, False, True, True, True, False, False, True, True, False, False, False, True, False, False, True, True, True, True, True, True, True, False, True, True, False, False, True, False, True, True, False, False, True, True, False, True, True, True, False, False, True, True, True, False, True, False, False, True, False, False, True, True, False, True, False, True, True, True, False, True, True, False, False, False, False, False, False, True, False, True, True, False, False, False, True, True, True, False, True, True, False, True, True, True, False, False, False], 105))
for test in tests:
tree = self.buildtree(test[0], degree)
self.checkcost(tree, test[1])
In[0]:
testsavetree = TestSaveTree()
suite = unittest.TestLoader().loadTestsFromModule(testsavetree)
unittest.TextTestRunner().run(suite)