Why is the number of children of the root_node growing in this tree generation algorithm?

Question

I'm writing an algorithm which creates a tree that contains n number of nodes with random (0..1) weights (a.k.a the value of the node). Simply a structure like

    root_node
    /      \
   *        *
  / \      / \
 *   *    *   *

I'm trying to figure out why instead of the tree structure like in the above image, it's actually the number of children nodes of the root_node which is growing upon each iteration, see my capitalized comment in the algorithm below.

class Node:
    def __init__(self, val, children=[]):
        self.val = val
        self.children = children


def create_random_weights_tree(tree_size):
    """
    Creates a balanced tree structure of `tree_size` elements; inits each node
    with a random value between 0 and 1, and returns the root_node of the tree.
    """
    root_node = Node(random.random())
    bottom_nodes = [root_node,]  # holds nodes located at bottom of the tree
    nodes_count = 1  # counts total number of nodes in the tree
    while nodes_count < tree_size:
        next_bottom_nodes = []
        # iterate through bottom tree nodes
        for node in bottom_nodes:
            print(node)
            if nodes_count + 2 > tree_size:
                # put in a last single node
                child = Node(random.random())
                node.children.append(child)
                next_bottom_nodes.append(child)
                nodes_count += 1
                break
            else:
                # add 2 children nodes
                children = [Node(random.random()), Node(random.random())]
                node.children.extend(children)
                next_bottom_nodes.extend(children)
                nodes_count += 2
            print(root_node)
            # WHY ARE THE  NUMBER OF CHILDREN OF THE ROOT NODE GROWING??
            print(len(root_node.children))
        bottom_nodes = next_bottom_nodes
    return root_node


root = create_random_weights_tree(10)

print statements output of the above code:

<__main__.Node object at 0x7f76675eb910>
<__main__.Node object at 0x7f76675eb910>
2
<__main__.Node object at 0x7f76675eb7f0>
<__main__.Node object at 0x7f76675eb910>
4
<__main__.Node object at 0x7f7651f3b880>
<__main__.Node object at 0x7f76675eb910>
6
<__main__.Node object at 0x7f7651118070>
<__main__.Node object at 0x7f76675eb910>
8
<__main__.Node object at 0x7f76511180d0>

score 0 · Accepted Answer · answered Nov 27 '20 at 10:39

This happens because of the default value that is assigned to the children parameter in the Node constructor.

In Python, such a default value is only evaluated once, not on every call of the constructor. As a consequence, all your calls to Node (which provide no second argument) will assign the same list to the children property. And so, every child that is added, is added to this single list, which you also see at root_node.children (but also the children property in every other node).

To fix your problem, use None as default value, and create the empty list within the constructor:

class Node:
    def __init__(self, val, children=None):
        self.val = val
        self.children = [] if children is None else children

Alternatively, you could create a copy of the argument:

class Node:
    def __init__(self, val, children=[]):
        self.val = val
        self.children = children[:]

But then the caller should realise that the list that they pass is not the one that gets assigned.

Why is the number of children of the root_node growing in this tree generation algorithm?

1 Answers1