# Computing all paths from root to the leaf nodes in a tree

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

• Can you replace the code with a pseudo-code? We do not deal with specific languages. – Steven Apr 16 '20 at 19:34

That is, $$paths(v)$$ returns a list $$L_v$$ of all paths from $$v$$ to the leaves of the subtree rooted in $$v$$.
If $$v$$ is a leaf, then the list $$L_v$$ returned by $$paths(v)$$ contains a single path consisting of $$v$$ itself.
If $$v$$ is not a leaf and $$u_1, \dots, u_k$$ are its children, then $$paths(v)$$ returns the union of $$k$$ lists $$L'_{u_1}, \dots, L'_{u_k}$$, where $$L'_{u_i}$$ is obtained by prepending $$v$$ to every path in $$L_{u_i}$$.
• The difference are: 1) if $v$ is a leaf, your version of $paths(v)$ returns an empty list (while in my solution returns a list containing $v$) and 2) If $v$ is not a leaf, your version of $paths(v)$ adds $u_i$ to the list $L_{u_i}$ returned by $paths(u_i)$ (while my solution adds $v$ to $L_{u_i}$). – Steven Apr 16 '20 at 19:50