How the process actually flows in branch sum python code

Question

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?

Can you give an example of object that would be fed into the function? You have a recursive function here. It is using a number (runningSum) and a list (sums) to track the cumulated sums per branch. The number is used to pass the value down in the recursive chain, the list to pass it up as it is mutable. — mozway
– mozway, Commented Dec 28, 2021 at 4:13
@mozway the binary tree and array is here: imgur.com/a/AtGnFRZ . i have edited the post — NroGamerz
– NroGamerz, Commented Dec 28, 2021 at 4:24

sahasrara62 · Accepted Answer · 2021-12-28 04:48:33Z

1

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

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

edited Dec 28, 2021 at 4:48

answered Dec 28, 2021 at 4:23

sahasrara62

11.4k3 gold badges35 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

Brandon Over a year ago

"once you got child node you are returning that sum" -- you mean "leaf" node here, and appending the sum, not returning it

sahasrara62 Over a year ago

yeah leaf node, and appending the result not reutrning it. updated

NroGamerz Over a year ago

Thank you i thought the same. So, first calculateBranchSums(node.left, newRunningSum, sums) runs right. the newRunningSum = 1+2 then calculateBranchSums(node.right, newRunningSum, sums) runs, the newRunningSum is still 1 or its 1+2? Whats calling function within the same function called?

sahasrara62 Over a year ago

@NroGamerz updated solution, yes here you have implemented pre-order traversal, ie Node-left-right

sahasrara62 Over a year ago

so it goes like this 1-> 1+2 -> 1+2+4 (left traversal over)-> 1+2 (right taversal start)-> 1+2+5 ( right travesal over) - > 1 (right traversal start) -> 1+3 -> 1+3+6 (left traversal over) - > 1+3 -> 1+3+7, now compare this traversal with the function call like how you calling revurive function where first left part is evaluated and then right part , more info you need to see how pre order traversal work and branch sum using pre order traversal in youtube

|

Collectives™ on Stack Overflow

How the process actually flows in branch sum python code

1 Answer 1

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest

Related