?Using Python

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 list of node labels that starts with the root and ends at a leaf. Each subsequent element must be from a label of 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 ordered in the output list from left to right in the tree. See the doctests for some examples.

def long_paths(t, n):

"""Return a list of all paths in t with length at least n.

>>> long_paths(Tree(1), 0)

[[1]]

>>> long_paths(Tree(1), 1)

[]

>>> 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, [Tree(13, [Tree(14)])])])

>>> whole = Tree(0, [left, Tree(13), mid, right])

>>> print(whole)

0

1

2

3

4

4

5

13

6

7

8

9

11

12

13

14

>>> for path in long_paths(whole, 2):

... print(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, 13, 14]

>>> for path in long_paths(whole, 3):

... print(path)

...

[0, 1, 3, 4]

[0, 1, 3, 4]

[0, 1, 3, 5]

[0, 6, 7, 8]

[0, 11, 12, 13, 14]

>>> long_paths(whole, 4)

[[0, 11, 12, 13, 14]]

"""

"*** YOUR CODE HERE ***"

The info about Tree

class Tree: """ >>> t = Tree(3, [Tree(2, [Tree(5)]), Tree(4)]) >>> t.label 3 >>> t.branches[0].label 2 >>> t.branches[1].is_leaf() True """ def __init__(self, label, branches=[]): for b in branches: assert isinstance(b, Tree) self.label = label self.branches = list(branches)

def is_leaf(self): return not self.branches

def map(self, fn): """ Apply a function `fn` to each node in the tree and mutate the tree.

>>> t1 = Tree(1) >>> t1.map(lambda x: x + 2) >>> t1.map(lambda x : x * 4) >>> t1.label 12 >>> t2 = Tree(3, [Tree(2, [Tree(5)]), Tree(4)]) >>> t2.map(lambda x: x * x) >>> t2 Tree(9, [Tree(4, [Tree(25)]), Tree(16)]) """ self.label = fn(self.label) for b in self.branches: b.map(fn)

def __contains__(self, e): """ Determine whether an element exists in the tree.

>>> t1 = Tree(1) >>> 1 in t1 True >>> 8 in t1 False >>> t2 = Tree(3, [Tree(2, [Tree(5)]), Tree(4)]) >>> 6 in t2 False >>> 5 in t2 True """ if self.label == e: return True for b in self.branches: if e in b: return True return False

def __repr__(self): if self.branches: branch_str = ', ' + repr(self.branches) else: branch_str = '' return 'Tree({0}{1})'.format(self.label, branch_str)

def __str__(self): def print_tree(t, indent=0): tree_str = ' ' * indent + str(t.label) + " " for b in t.branches: tree_str += print_tree(b, indent + 1) return tree_str return print_tree(self).rstrip()