Why is the recursion returning NoneType in the following code of segment Tree?

Question

I tried to build segment tree using python, using which I can get sum of digits in array 'arr' from index (l,r). I am getting expected tree correct but it shows error when I call getSum().

from math import ceil,log2
def build(arr,tree,node,start,end):
    if start==end:
        tree[node] = arr[start]
        return tree[node];
    mid = (start+end)//2
    tree[node] = build(arr,tree,2*node + 1,start, mid) + build(arr,tree,2*node + 2,mid+1, end)
    return tree[node]
def getSum(tree,node,start,end,l,r):
    if(r<start or l>end):
        return 0
    elif r>=end and l<=start:
        return tree[node]
    else:
        mid = (start+end)//2
#         print(getSum(tree,2*node + 1,start,mid,l,r))
#         print(getSum(tree,2*node+2,mid+1,end,l,r))
        getSum(tree,2*node + 1,start,mid,l,r) + getSum(tree,2*node+2,mid+1,end,l,r)
if __name__=='__main__':
    tree = [0]*((2)**(ceil(log2(5))+1)-1)
    build([1,2,3,4,5],tree,0,0,4)
    getSum(tree,0,0,4,1,3)

error : unsupported operand type(s) for +: 'NoneType' and 'int'

Answer 1

You didn't return the sum of the subtrees. because of that it's returning None. you should write like this.

    return getSum(tree,2*node + 1,start,mid,l,r) + getSum(tree,2*node+2,mid+1,end,l,r)