Your task is to find a path from a node to a node in a given tree. A path is a route in the tree that follows the connections between the nodes.
For example, in the tree below, the path from the node to the node is , and the path from the node to the node is .
In a file treepath.py
, implement the function find_path
, whose parameters are a reference to the root of a tree and the node identifiers and . The function returns the path as a list, or None
if there is no path.
class Node: def __init__(self, value, children=None): self.value = value self.children = children if children else [] def __repr__(self): if self.children == []: return f"Node({self.value})" else: return f"Node({self.value}, {self.children})" def find_path(node, a, b): # TODO if __name__ == "__main__": tree1 = Node(1, [Node(4, [Node(3), Node(7)]), Node(5), Node(2, [Node(6)])]) print(find_path(tree1, 3, 2)) # [3, 4, 1, 2] print(find_path(tree1, 1, 7)) # [1, 4, 7] print(find_path(tree1, 5, 5)) # [5] print(find_path(tree1, 7, 3)) # [7, 4, 3] print(find_path(tree1, 4, 8)) # None tree2 = Node(1, [Node(2, [Node(3, [Node(4)])])]) print(find_path(tree2, 1, 4)) # [1, 2, 3, 4] print(find_path(tree2, 4, 1)) # [4, 3, 2, 1] print(find_path(tree2, 2, 3)) # [2, 3] tree3 = Node(1, [Node(2), Node(3), Node(4)]) print(find_path(tree3, 2, 3)) # [2, 1, 3] print(find_path(tree3, 1, 2)) # [1, 2] print(find_path(tree3, 5, 5)) # None