Finding paths to a value in a tree-CodePudding

Imagine that you are to write a function, that takes in as arguments a tree and a value x. The function has to return all the paths from the root of the tree to that value, in a form of list. If there are multiple paths, then the function returns a list of lists.

Here is what I got so far

def path_finder(t,value):
    paths = []
    if label(t) == value:
       return [label(t)]
    for b in branches(t):
       path = path_finder(b, value)
       if path:
         paths.append([label(t)] path)
    return paths

However, given the tree t and the value x = 5, here is my output

t = tree(1, [tree(2, [tree(3), tree(4, [tree(6)]), tree(5)]), tree(5)])

path_finder(t,5)

[[1,[2,5]],[1,5]]

Seems to be a stacking problem.

Any help debugging it?

Note: label(t) --> the value of the root

CodePudding user response：

I don't know whether there is a standard tree class that you are using, so I made one.

class tree():
    def __init__(self, val, sub=[]):
        self.val = val
        self.sub = sub # a list of trees

def label(t):
    return t.val
def branches(t):
    return t.sub

def path_finder(t, value):
    paths = []
    if label(t) == value:
        paths.append([value])
    for b in branches(t):
        paths  = [[label(t)]   path for path in path_finder(b, value)]
    return paths

t = tree(1, [tree(2, [tree(3), tree(4, [tree(6)]), tree(5)]), tree(5)])
for x in range(7):
    print(x, path_finder(t, x))

The main correction is at the line paths = [[label(t)] path for path in path_finder(b, value)]. Also note that when label(t) == value, I am not immediately returning a list. Stopping the code at that moment won't find every path, for example, when a node 5 is under another node 5.

Output:

# 0 [] # when path_finder cannot find the value
# 1 [[1]]
# 2 [[1, 2]]
# 3 [[1, 2, 3]]
# 4 [[1, 2, 4]]
# 5 [[1, 2, 5], [1, 5]]
# 6 [[1, 2, 4, 6]]