Python return an element from recursive DFS

Question

This relates to how Python is both pass by reference or pass by value depending on if the object is immutable or not. I'm able to traverse a binary tree recursively and print out all the values, but it's a little more difficult if I want to instead return a specific element. In the code below, I'm (twice) trying to return a node if its data attribute matches the integer passed in. n1 and n2 are those int values.

def get_node(self, d, root, n=[]):
    if (root == None):
        return
    else:
        if(root.data == d):
            n.append(root)
        self.get_node(d,root.left)
        self.get_node(d, root.right)
        return n



def tree_traversal(self, n1, n2):
    n1 = self.get_node(n1,self.root)[0]
    n2 = self.get_node(n2,self.root)[1]
    print(n1.data)
    print(n2.data)
    return self.helper(n1,n2)

This works, and I get a list that contains the node objects I'm looking for. However, if instead of returning (and passing as an argument) a list, I use a string, or a None object to later be changed, this doesn't work. I assume that's because lists are mutable while strings are not. What's more, you'll see I have to assign n[1] to n2 because for some reason, even after exiting the get_node recursive call and doing it all over again for n2, the returned list still contains n1 in the 0th index.

Can someone please explain why the list is still modified when assigning to n2? And is there a way to instead of passing as argument and returning an empty list n, passing as argument and returning a regular object that has default value None?

Answer 1

Your first problem is this:

def get_node(self, d, root, n=[]):

There are lots of warnings about not using mutable data to default an argument as you did. We're not talking about pass by reference nor pass by value here (Python only passes by value -- it passes pointers to containers by value -- passing by reference is something else altogether.) The problem here is that the default value is only evaluated once, so all subsequent calls will use the same structure.That's why you:

have to assign n[1] to n2 because for some reason, even after exiting the get_node recursive call and doing it all over again for n2, the returned list still contains n1 in the 0th index

Now you know the reason. This is nearly identical to using a global to store results during your recursion. Avoid it.

Your functions don't seem to be designed properly. If we're working with a tree, then we should be able to do get_node() or tree_traversal() at any point in the tree, there should be no fixed root in the code. Also, making n1 and n2 have different types and meanings in the same function is confusing -- use different variable names. Let's try it this way:

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

        assert (data is not None), "Error in tree/model logic!"

        self.data = data
        self.left = left
        self.right = right

    def get_node(self, d):

        if self.data == d:
            return self

        if self.left is not None:
            result = self.left.get_node(d)
            if result is not None:
                return result

        if self.right is not None:
            result = self.right.get_node(d)
            if result is not None:
                return result

        return None

    def tree_traversal(self, n1, n2):
        node1 = self.get_node(n1)
        node2 = self.get_node(n2)

        return node1, node2

root = Node(0)
root.left = Node(1, Node(2), Node(3, Node(4)))
root.right = Node(5, Node(6), Node(7, Node(8), Node(9)))

print(root.tree_traversal(3, 9))

Now, let's discuss how this does or doesn't fit your model.