python linked structure - inserting child to node A's parent is also inserting to node A

Question

I'm trying to implement a linked structure for a tree using python this is an extract of my code

class Node(object):
    def __init__(self,value,father=None,children=[]):
        self.value=value
        self.father=father
        self.children=children
    def __str__(self):
        return self.value

class Tree(object):

    def __init__(self,root=None):
        self.root=root
    def insertNode(self,new_node,father_value):
        father_node=self.find_node(father_value)
        if not father_node:
            return False
        new_node.father=father_node
        print("Node's information BEFORE adding child to father's list of children")
        print(f"Father node (find) {father_node}")
        print(f"Father node's children {[x.value for x in father_node.children]}")
        print(f"New node's father {new_node.father}")
        print(f"New node's children {[x.value for x in new_node.children]}")
        father_node.children.append(new_node)
        print("Node's information AFTER adding child to father's list of children")
        print(f"Father node (find) {father_node}")
        print(f"Father node's children {[x.value for x in father_node.children]}")
        print(f"New node's father {new_node.father}")
        print(f"New node's children {[x.value for x in new_node.children]}")

    def find_node(self,value):
        stack=[self.root]
        while True:
            if len(stack)==0:
                return False
            node=stack.pop()
            if node.value==value:
                return node
            children=node.children
            stack.extend(children)

n1=Node("A")
tree=Tree(n1)
tree.insertNode(Node("B"),"A")

n1=Node("A")
tree=Tree(n1)
tree.insertNode(Node("B"),"A")

the OUTPUT is

Node's information BEFORE adding child to father's list of children

Father node (find) A
Father node's children []
New node's father A
New node's children []
Node's information AFTER adding child to father's list of children
Father node (find) A
Father node's children ['B']
New node's father A
New node's children ['B']

As you can see, when I append the new inserted node into the father's children list it also inserts into the new node's list of children. How to fix this?

Answer 1

The problem occurs because of how Python deals with default values of optional parameters of a function.

In class Node(object), you have this line:

def __init__(self,value,father=None,children=[]):

Python evaluates the default value [] only once (creating an empty list object), and then reuses that evaluated value (reference to that list object) for all subsequent invocations of that function.

In your case the function is the __init__() function, which gets invoked each time you instantiate the Node class. If you instantiate Node multiple times without explicitly passing in a third argument, in all those invocations of __init__(), the parameter children gets assigned the same list object as the default value. You are using this value to set the children attribute of all these instances. In other words, for all those Node instances, the children attribute would be pointing to the same list object. That is why inserting a child to the "father" Node is also adding the same child to the current Node.

The correct way to re-write __init__() would be:

class Node(object):
    def __init__(self,value,father=None,children=None):
        self.value=value
        self.father=father
        self.children=children if children is not None else []

Moral

The general moral here is that, if your parameter's default value is a mutable object, it can throw surprises like this -- where, unknown to you, multiple references are stored to a single object, and mutations (changes) to the object through one reference, will also get reflected (seen) through the other references.

This is all documented here