I have a this tree, i want to print out all paths from root to all child nodes:
NOTE: I wanted to come up with a solution that does not involve passing state between recursive calls.
a / | \ b c d / \ \ e f g / / | \ h i j k
This is the my code to create and print the paths.
class Node: def __init__(self, data, children=): self.data = data self.children = children tree = Node( "A", children=[ Node("B", children=[Node("E"), Node("F")]), Node("C"), Node("D", children=[Node("G", [Node("H"), Node("I"), Node("J"), Node("K")])]), ], )
i want to enumerate all the paths to reach from root node to all leaf nodes.This is what i have come up with.
def paths(root): x =  if root.children: for c in root.children: for el in paths(c): x.append(c.data + el) else: x.append("") return x a = paths(tree) print(a)
i get this output:
['BE', 'BF', 'C', 'DGH', 'DGI', 'DGJ', 'DGK']
This is partially correct, what is missing is the root node 'A' in all the paths, I am not able to think how to get that, even after thinking for 2 hours straight. I know why is it happening(because I start from child nodes of the root). what i cannot get is how to encode the root node itself.
I hope this pseudocode is clear:
function paths(N): path <- empty list if the node(N) has children for every child node `(C)` of `N` for every path `(P)` in paths(`C`) add to path <- `C.data` + `P` otherwise add to path <- + "" return path