I am really sorry for asking this simple question. I am currently solving algorithms and got stuck in branch sum. I searched a lot around but nobody actually explained the actual code, just the concept. If anyone here will be kind enough to explain it to me.

class BinaryTree:
def __init__(self, value):
self.value = value
self.left = None
self.right = None

def branchSum(root):
    sums = []
    calculateBranchSum(root, 0, sums)
    return sums

def calculateBranchSums(node, runningSum, sums):
    if node is None:
        return
    newRunningSum = runningSum   node.value
    if node.left is None and node.right is None:
        sums.append(newRunningSum)
        return
    calculateBranchSums(node.left, newRunningSum, sums)
    calculateBranchSums(node.right, newRunningSum, sums)

I am mainly confused on how the node goes back? Like first with node.left, we receive the final sum. Then with node.right, newRunningSum is last sum?

CodePudding user response：

node is not going back, you are just saving the result of running sum and passing that to next nodes and once you got child node(leaf node) you are appending sum and return nothing, and this sum is your branch sum

     1
   /  \
  2    3
  /\   /\
 4  5  6 7

for example, in above tree, this is how your code flows

1 -> (1 2), (1 3) -> ((1 2 4), (1 2 5)),((1 3 6), (1 3 7)) 

and it reached the child node so the sum will be added in the resultant array ie sum_ (7,8,10, 11) will be the final result.

so running order in this case is:

 1  (node)
 1 2  (node.val node.left.val)
 1 2 4 - > (node.val   node.left.val  node.left.left.val) save this in array
 1 2 5 ->(node.val node.left.val node.left.right.val) save this in array
 1 3   (node.val node.right.val)
 1 3 6 ->(node.val node.right.val node.right.left.val) save this in array
 1 3 7 -> (node.val node.right.val node.right.right.val) save this in arry