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

1 Answer 1

Reset to default
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}$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ i added the pseudocode, hopefully my approach is clear with that. $\endgroup$ Commented Apr 16, 2020 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$ Commented Apr 16, 2020 at 19:50

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.