how to write a recursive function that sums the integers in a tree?-CodePudding

Write a recursive function TreeSum(T) to add up all the integers in a tree. My test case is

TreeSum(set)

48

where

set=[[[[2,1],[3,7]],[1,2]],[[0,6],[[[3,2],[1,1]],[9,10]]]]

This is the code I have so far:

def TreeSum(T):
     if len(T)==0:
       return 0
     else:
       return T[0]   TreeSum(T[1:])

I am getting an error from the return line ("can only concatenate list (not "int") to list"). How can I fix this? Error:

----> 5    return T[0]   TreeSum(T[1:])
      6 
      7 TreeSum(maple)

TypeError: can only concatenate list (not "int") to list

CodePudding user response：

@j1-lee had the correct approach, but this is limited in terms of span of the sublists (silently ignoring the items with a position > 1, or failing if one of the first two elements is an integer). You need to apply the recursive function on all sub-elements. One way is to use map

NB. I slightly changed the input to add two more elements to the first sublist

tree = [[[[2,1],1,[3,7],[1]],[1,2]],[[0,6],[[[3,2],[1,1]],[9,10]]]]

def treesum(x):
    if not isinstance(x, list):
        return x
    return sum(map(treesum, x))
print(treesum(tree))

Output: 50