Unexpected behavior with simple tree class

Question

I am writing a learning program in python, and I'm not getting the behavior I'm expecting. I am attempting to create a really basic tree with a class called node. Please don't punish me for having a crappy tree design, I'm just trying to learn the language.

Anyway, I'm expecting output like:

LEVEL1 0
LEVEL1 1

But, I'm getting

LEVEL1 0
LEVEL1 1
LEVEL1 0 ... LEVEL2 0

On the line where I do leaves[0].addLeaf I really thought I would be calling a method of of one of the children leaves, but it appears that I am instead calling from the TOP leaf. Please help me understand.

Don't be tricked by the name traversePrint. Nothing is being traversed, not yet anyway :(

#!/usr/bin/python

class node:
    """Something that can act like like leaves of a tree"""
    leaves = []
    def __init__(self, data=""):
        self.data = data
    def addLeaf(self, newNode="new"):
        self.leaves.append(node(newNode))
    def printLeafs(self):
        for leaf in self.leaves:
            print leaf.data
    def getLeafs(self):
        return self.leaves
    def traversePrint(self):
        for leaf in self.leaves:
            print leaf.data
        #for leaf in self.leaves:
        #   leaf.traversePrint()

top = node("TOP")
top.addLeaf("LEVEL1 0")
top.addLeaf("LEVEL1 1")

leaves = top.getLeafs()
leaves[0].addLeaf("LEVEL1 0 ... LEVEL2 0")

top.traversePrint()

Welcome to stackoverflow! You've managed to get your code to display properly, which is a very good start! I've made some minor edits to your post to format it a little better. — TooTone, Sep 18 '13 at 23:22

score 4 · Accepted Answer · edited May 23 '17 at 12:20

Your problem is that right now, leaves is a class-level attribute. You want it to be an instance-level attribute, so that the list isn't shared between all the instances. See this SO question for some details on the difference.

Luckily, making leaves an instance attribute is easy to do: remove the line leaves = [] and instead, change your __init__ method to include the line self.leaves = [].

def __init__(self, data=""):
    self.data = data
    self.leaves = [] # Create a new list to hold this instance's children!

To see more clearly what's going on in your original code, try editing your addLeaf method by adding print([leaf.data for leaf in self.leaves]) after you add the leaf. In your original code, this will print out:

['LEVEL1 0']
['LEVEL1 0', 'LEVEL1 1']
['LEVEL1 0', 'LEVEL1 1', 'LEVEL1 0 ... LEVEL2 0']

Of course, you only want one leaf to be shown on the third printout, because you're accessing a different node, but instead you got all three! This is because when the list is at the class level, all the instances of node share the same leaves list. When you move the list initialization inside the __init__ method, you see the expected results from your three addLeaf calls:

['LEVEL1 0']
['LEVEL1 0', 'LEVEL1 1']
['LEVEL1 0 ... LEVEL2 0']

score 3 · Answer 2 · answered Sep 18 '13 at 23:28

Because you define leaves at the class level, all instances of node share a single leaves list. I doubt that's what you intended. If you want each node to have its own leaves list, then move the assignment into __init__ instead:

    # leaves = [] # REMOVE THIS LINE
    def __init__(self, data=""):
        self.data = data
        self.leaves = []  # ADD THIS LINE

Then the output is:

LEVEL1 0
LEVEL1 1

and adding:

leaves[0].traversePrint()

prints:

LEVEL1 0 ... LEVEL2 0

Clear?

score 2 · Answer 3 · answered Sep 18 '13 at 23:22

leaves is a class attribute so all addLeaf does is adds to that single attribute as all nodes are objects of class node (btw rename it to Node)

What you want is per node attribute leaves, hence add it as instance attribute i.e. in __init__ add self.leaves = []

Unexpected behavior with simple tree class

3 Answers3