Find root to leaf path with given sum. Code succeeds with string, fails with list

I am looking at a binary tree problem. The goal is to find all path(s) from root to leaf, such that the values on the path sum up to a given k.

For that purpose I have written the same algorithm in two different ways:

1. The first version uses a string parameter a.
2. The second version uses a list parameter a.

They are supposed to give the same path result, but the second version prints a path that includes almost all the values in the tree.

Version 1

def rootToLeafPathsSumToK(root, k, a):
    if root == None :
        return None
    
    if root.left==None and root.right==None:
        if root.data==k:
            print(a+ str(root.data)+" ")
        return

    a+=str(root.data)+" "
    rootToLeafPathsSumToK(root.left,k-root.data,a)
    rootToLeafPathsSumToK(root.right,k-root.data,a)

output:

5 6 2 
5 7 1 

Version 2

def rootToLeafPathsSumToK(root, k, a):
    if root == None :
        return None
    
    if root.left==None and root.right==None:
        if root.data==k:
            a.append(root.data)
            print(a)
        return

    a.append(root.data)
    rootToLeafPathsSumToK(root.left,k-root.data,a)
    rootToLeafPathsSumToK(root.right,k-root.data,a)

Answer

The difference between these two code snippets is:

• In the first version, where a is a string, you execute a+=str(root.data)+" ". This creates a new string and assigns it to the local variable a. This operation does not affect the string that the caller had passed as argument. Moreover, strings are immutable in Python.

• In the second version, where a is a list, you execute a.append(root.data). This does not create a new list. It mutates the list that the caller had passed as argument. In fact, that code only has one list. So all append calls affect that single list.

So, where in the first version, the effect of adding a value is local and does not impact the caller’s string, in the second version the effect is reaching also to the caller, since they use the same list.

To apply the same local principle in the second code version, replace the call to append with this:

a = a + [root.data]

Now the original list a is not mutated. Instead a new list is created, and assigned back to the local variable a. But here, the caller’s list is still the original list. There is now a new list created.