Sum of number in a binary tree

December 11, 2021

I have a list that can contain either two natural numbers or two more lists. Each of these lists also contains either two integers or two further lists, and so on.
e.i.: [[4, 7], [[3, 5], [9, 1]]]
I need to use recursion to calculate the sum of all the numbers in the tree and write the following code:

def getSum(tree):
    sum = 0
    for elemente in tree:
        if type(elemente)==int:
            sum += elemente
        else:
            sum = getSum(elemente)
    return sum

The code doesn’t work because it returns sum always to 12, so my question is, how can I make it work but still using recursion?. Have I not recognize the base case correctly?

>Solution :

Here is how you can do it:

def getSum(tree):
    sum = 0
    for elemente in tree:
        if type(elemente)==int:
            sum += elemente
        else:
            sum += getSum(elemente)
    return sum

tree = [[4, 7], [[3, 5], [9, 1]]]
print(getSum(tree))

Alternatively, you can keep track of the sum outside the recursion loop.

For example like this:

def getSum(tree, sum = None):
    sum = sum or 0
    for elemente in tree:
        if type(elemente)==int:
            sum += elemente
        else:
            sum = getSum(elemente, sum)
    return sum

tree = [[4, 7], [[3, 5], [9, 1]]]
print(getSum(tree))