Python - unusual behaviour with custom tree

Question

I needed to sort a list in a very specific way by using a tree in a Python script, so I wrote my own quick TreeNode class. However, I have found very odd behaviour when appending a child to a node and I really cannot understand what is going on.

Here is the class:

class TreeNode:

    children = []
    identity = ""

    def __init__(self, node_id, c = []):
        self.identity = node_id
        self.children = c

    def get_id(self):
        return self.identity

    def append_child(self, child):
        self.children.append(child)

    def remove_child(self, child):
        self.children.remove(child)

    def get_children(self):
        return self.children

    def walk(self):
        yield self
        for child in self.children:
            for n in child.walk():
                yield n

    def find_id(self, node_id):
        if self.identity == node_id:
            return self
        for child in self.children:
            found = child.find_id(node_id)
            if found:
                return child
        return None

What is happening is that when I append a child to the tree, the child's list of children is instantiated with length one, and that first element is a reference back to that same child. And, so, that first element in the children has a children list of length one too, also refering to the same node, and it goes on seemingly ad infinitum.

Here is a visualisation of the "tree" after just a single element has been appended to the root node...

I have no clue what is happening here and I hope that somebody else who is more familiar with Python might be able to enlighten me. It's been bugging me all afternoon!

Answer 1

def __init__(self, node_id, c = []):

The problem is your c = []. Default arguments to functions are evaluated exactly one time in Python. So the first time you initialize a TreeNode and change c, that c will retain the changed value the next time you create a new TreeNode, because it's a list and they won't create new lists each time, they'll just keep referring to the exact same list. You'll be initializing the child node with the same child list that the parent had.

This is what you want instead:

def __init__(self, node_id, c = None):
    if c is None:
        c = []

This works because you're creating a new empty list every time you initialize a TreeNode. In the previous setup, you were modifying the exact same list every time, because of the issue Kevin linked to in his comment.