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 &lt;- 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 &lt;- `C.data` + `P`
   otherwise
      add to path &lt;- + ""
   return path
The problem is that each node is adding its children to the list of paths. Instead, you can modify your recursive function so that each node only adds itself.

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}$.