Finding a path using the Parents Array Recursively in Python

Question

So I have a task, that is, to write a function that takes a parents array produced by a traversal, a starting vertex, and an end vertex, and produces a path from the start vertex to the end vertex.

I have tried writing the code for this

def tree_path(parents, start, end):
    if ((start == end) or (end == -1)):
        return [start, end]
    else:
        return tree_path(parents, start, parents[end])

It doesn't do what I intended for it to do. I'm not very good at recursion. Any help would be much appreciated. Thanks

Answer 1

You can try, assuming we want a list of all vertices from start to end, the following:

def tree_path(parents, start, end):
    if (start == end) or (end == -1):
        return [start]
    else:
        return tree_path(parents, start, parents[end]) + [end]

If start coincides with end then our path consists only of one vertex: start. Otherwise, we find the path from start to the parent of end and to this path we add the end node.