python - Enumerating all paths in a tree and manipulate values associated with each node

Question

Inspired by the answer to the question "Enumerating all paths in a tree", I wrote an adapted version (I don't need the unrooted path):

def paths(tree):
    #Helper function
    #receives a tree and 
    #returns all paths that have this node as root
    if not tree:
        return []
    else: #tree is a node
        root = tree.ID
        rooted_paths = [[root]]
        for subtree in tree.nextDest:
            useable = paths(subtree)
            for path in useable:
                rooted_paths.append([root]+path)
    return rooted_paths

Now, in my "tree" object, I have a number associated with each node: tree.number. I looks like this:

     A,2
    /   \
  B,5   C,4
   |    /  \
  D,1  E,4 F,3

I would like to initialize my paths with a 0 value, and sum all tree.numbers of the path, in order to know the sum for each generated path:

A-B-D: 8
A-C-E: 10
A-C-F: 9

How should I modify my code to get this result? I'm not seeing how to do it.

Answer 1

In order to achieve what you want, pass one more argument to the recursion - that would be the sum you have got so far. Also return one more value for each path - its sum:

def paths(tree, sum_so_far):
    #Helper function
    #receives a tree and 
    #returns all paths that have this node as root
    if not tree:
        return []
    else: #tree is a node
        root = tree.ID
        val = tree.Value
        rooted_paths = [[[root], value]]
        for subtree in tree.nextDest:
            useable = paths(subtree, sum_so_far + val)
            for path in useable:
                rooted_paths.append([[root]+path[0], path[1]])
    return rooted_paths

Something like this should work. Please note now you are returning an array of pair of path and integer value. The integer value is the sum along that path.

Hope that helps.