Python - Calculating branch sum of Binary Tree

Question

So I am solving an algoExpert.io problem, The question is to write an algorithm to calculate all branch sums left to right. The issue is the tests pass depending on how I call the helper function and I really cannot find why.

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

def branchHelper(root, sums=[], branchSum=0):
    if root is None:
        return

    branchSum += root.value
    if root.left is None and root.right is None:
        sums.append(branchSum)

    branchHelper(root.left, sums, branchSum)
    branchHelper(root.right, sums, branchSum)
    return sums

So this is all good so far and,

def branchSums(root): 

    sums = []                       #
    return branchHelper(root, sums) # Pass

This works fine as can be seen from this picture.

But soon as I do this (Which was my original solution):

def branchSums(root): 
    return branchHelper(root) # Fail

Why does using default sums=[] fail in this manner?

This is the error message. I can see that the test case used root 1 and left child 3. And my code spit out [1, 3] when I use the second method.

I really can't make sense of this, any help would be appreciated.

alex2007v · Accepted Answer · 2020-02-13 07:21:47Z

3

It because of your second sums params that has default value.

If you rewrite it next you will pass your test

def branchHelper(root, sums=None, branchSum=0):
    if root is None:
        return

    if sums is None:
        sums = []

    branchSum += root.value
    if root.left is None and root.right is None:
        sums.append(branchSum)
    branchHelper(root.left, sums, branchSum)
    branchHelper(root.right, sums, branchSum)
    return sums

An example why it's wrong:

def wrong_func(append_item, items=[]):
    items.append(append_item)
    return items

wrong_func(1) # output [1]
wrong_func(2) # output [1, 2]


def correct_func(append_item, items=None):
    if items is None:
        items = []
    items.append(append_item)
    return items

correct_func(1) # output [1]
correct_func(2) # output [2]

The first time that the function is called, python creates a persistent list. Every subsequent call to append appends the value to that original list. That's what happens when algoExpert.io test your code.

And that's why first test passed and second failed (first test binary tree with one item 1, second test does next check with 1, 2, and it appends new value to your sums list, and you got failed test.

edited Feb 13, 2020 at 7:21

answered Feb 13, 2020 at 7:15

alex2007v

1,3109 silver badges12 bronze badges

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

2 Comments

zcahfg2 Over a year ago

Oh my, the default value is persistent! wow, that finally made a total sense. I should really be careful about this. Any reason for the designer to make the default value persistent?

zcahfg2 Over a year ago

found out this link: effbot.org/zone/default-values.htm Many thanks to @alex2007v for teaching me this!

Collectives™ on Stack Overflow

Python - Calculating branch sum of Binary Tree

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related