CODEWITHSUNDEEP
pythonpython-3.xalgorithmbinary-tree
zcahfg2
zcahfg2

Reputation: 881

Python - Calculating branch sum of Binary Tree

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. enter image description here

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

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

enter image description here

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

enter image description here

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.

Upvotes: 3

Views: 898

Answers (1)

alex2007v
alex2007v

Reputation: 1300

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.

Upvotes: 3

Related Questions