Different behavior recursing binary tree to output list v. string

Question

I'm learning recursion through binary trees with python.

I'm not understanding the discrepancy in the output of these two functions. In the first one, I'm coding the traversal to return a list, in the second a string.

For the list:

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

class Tree:
    def __init__(self):
        self.root = None

    def inorder(self, data, traversal=[]):        
        if data:
            self.inorder(data.left, traversal)
            traversal.append(str(data.value))
            self.inorder(data.right, traversal)

        return traversal
"""
       1
      / \
     2   3
    / \   
   4   5
"""
thing = Tree()
thing.root = Node(1)
thing.root.left = Node(2)
thing.root.right = Node(3)
thing.root.left.left = Node(4)
thing.root.left.right = Node(5)

print(thing.inorder(thing.root))

['4', '2', '5', '1', '3']

However, if i modify the inorder function to return a string:

    def inorder(self, data, traversal=""):        
        if data:
            self.inorder(data.left, traversal)
            traversal += str(data.value)
            self.inorder(data.right, traversal)

        return traversal

'1'

It only works if i assign the output of the recursive calls to traversal, like this:

    def inorder(self, data, traversal=""):        
        if data:
            traversal = self.inorder(data.left, traversal)
            traversal += str(data.value)
            traversal = self.inorder(data.right, traversal)

        return traversal

'42513'

I'm not understanding why the behavior is different if i append to a list rather than concatenate a string. Can someone explain it to me?

https://stackoverflow.com/questions/373419/whats-the-difference-between-passing-by-reference-vs-passing-by-value — Abhinav Mathur, Oct 16 '21 at 04:25

score 2 · Accepted Answer · answered Oct 16 '21 at 06:10

Strings in python are immutable. Your traversal accumulator relies on mutation to work. Rather than relying on mutating your "traversal" data structure, you can modify it to actually use the return value(s).

if data:
    t1 = self.inorder(data.left, "")
    t2 = data.value
    t3 = self.inorder(data.right, "")
    traversal = t1 + t2 + t3

You could (probably) use the same technique for lists. And at that point, you would no longer need to pass the accumulator along on the recursive calls.

Different behavior recursing binary tree to output list v. string

1 Answers1