?Using Python Implement long_paths, which returns a list of all paths in a tree
ID: 3917434 • Letter: #
Question
?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()
Explanation / Answer
Here is the program in python. Please comment below for any queries or modifications. I will help with that. Thank you.
class Node:
def __init__(self, dataa):
self.dataa = dataa
self.L = None
self.R = None
def Print_Paths(root):
path = []
Print_Paths_Rec(root, path, 0)
def Print_Paths_Rec(root, path, Path_length):
if root is None:
return
if(len(path) > Path_length):
path[Path_length] = root.dataa
else:
path.append(root.dataa)
Path_length = Path_length + 1
if root.L is None and root.R is None:
Array_Print(path, Path_length)
else:
Print_Paths_Rec(root.L, path, Path_length)
Print_Paths_Rec(root.R, path, Path_length)
def Array_Print(ints, len):
for i in ints[0 : len]:
print(i," ",end="")
print()
root = Node(10)
root.L = Node(8)
root.R = Node(2)
root.L.L = Node(3)
root.L.R = Node(5)
root.R.L = Node(2)
Print_Paths(root)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.