0
$\begingroup$

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
$\endgroup$
  • $\begingroup$ Can you replace the code with a pseudo-code? We do not deal with specific languages. $\endgroup$ – Steven Apr 16 at 19:34
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ i added the pseudocode, hopefully my approach is clear with that. $\endgroup$ – anekix Apr 16 at 19:42
  • $\begingroup$ 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}$). $\endgroup$ – Steven Apr 16 at 19:50
  • $\begingroup$ thankyou, let me try this out :) $\endgroup$ – anekix Apr 16 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.