Derive path in nested list tree structure (python)-CodePudding

I have created a tree data structure using a nested list in python. I have code which works through the list and prints a list of of all nodes and their parent node:

def printParents(node,adj,parent):
    if (parent == 0):
        print(node, "-> root")
    else:
        print(node, "->", parent)
    for cur in adj[node]:
        if (cur != parent):
            printParents(cur,adj,node)

The result is:

1 -> root
2 -> 1
3 -> 1
10 -> 3
11 -> 3
14 -> 11
15 -> 11
16 -> 11
17 -> 11
18 -> 11
19 -> 11
4 -> 1
5 -> 1

I am struggling to write a function which works backward to derive the path back to root given a specific node. For example with the input of 17 it should return something like 17 -> 11 -> 3 -> 1 (output format can vary).

Any help would be greatly appreciated. I am not a super experienced code so answers that treat me like I'm dumb would be appreciated.

CodePudding user response：

You could use a generator, that builds the path when coming back from recursion:

def paths(adj, node, parent=None):
    yield [node]
    for child in adj[node]:
        if child != parent:
            for path in paths(adj, child, node):
                yield [*path, node]

Here is how to call it:

# example tree
adj = [
    [1],
    [0,2,3,4,5],
    [1],
    [1,10,11],
    [1],[1],[],[],[],[],[3],
    [3,14,15,16,17,18,19],
    [],[],[11],[11],[11],[11],[11],[11]
]

for path in paths(adj, 0):
    if len(path) > 1:
        print(" -> ".join(map(str, path[:-1]))   " -> root")

This will output:

1 -> root
2 -> 1 -> root
3 -> 1 -> root
10 -> 3 -> 1 -> root
11 -> 3 -> 1 -> root
14 -> 11 -> 3 -> 1 -> root
15 -> 11 -> 3 -> 1 -> root
16 -> 11 -> 3 -> 1 -> root
17 -> 11 -> 3 -> 1 -> root
18 -> 11 -> 3 -> 1 -> root
19 -> 11 -> 3 -> 1 -> root
4 -> 1 -> root
5 -> 1 -> root

If you want to only output the paths that start at a leaf, then change the generator function to:

def paths(adj, node, parent=None):
    children = [child for child in adj[node] if child != parent]
    if not children: # it's a leaf
        yield [node]
    else:
        for child in children:
            for path in paths(adj, child, node):
                yield [*path, node]

Corresponding output:

2 -> 1 -> root
10 -> 3 -> 1 -> root
14 -> 11 -> 3 -> 1 -> root
15 -> 11 -> 3 -> 1 -> root
16 -> 11 -> 3 -> 1 -> root
17 -> 11 -> 3 -> 1 -> root
18 -> 11 -> 3 -> 1 -> root
19 -> 11 -> 3 -> 1 -> root
4 -> 1 -> root
5 -> 1 -> root