Python tree implementation - node reference

Question

I have this code to implement a tree in Python. One of the functions is to find the sum of the values of all nodes below (including itself), but this is not working.

I think the reason is because, once I create a node, I can't go back and access it with Node (name, value) - that would create a new node with that name and value, rather than referring to the one in the tree with that name and value, that has children linked to it.

Therefore, the sum_below function is just returning the value of the node. How I can reference the nodes in the tree:

class Node(object):
    def __init__(self, name, value):
        self.name = name
        self.value = value
        self.children = []

    def add_child(self, obj):
        self.children.append(obj)

    def sum_below(self):
        if self.children == []:
            return self.value
        else:
            ret = self.value
            for child in self.children:
                ret += child.sum_below()
            return ret
    def __str__(self, level = 0):
        ret = "\t"*level+repr(self.value)+"\n"
        for child in self.children:
            ret += child.__str__(level+1)
        return ret

[Edit] My problem is that once I create a node I can't reference it:

#In [2]:

Node(1,100)
parent = Node(1,100)
child = Node(2, 200)
parent.add_child(child)

#In [5]:

print parent

#Out [5]:

100
    200

#In [6]:

print Node(1,100)

#Out [6]:

100

So you see, parent, and Node(1,100) are not referencing the same things.

[EDIT]

#In [5]:
parent.sum_below()
#Out[5]:
300
#In [6]:
Node(1,100).sum_below()
#Out[6]:
100

In the code above, Node(1,100).sum_below() should be equal to parent.sum_below(), because they should be referring to the same node, but they're not.

Answer 1

This answer refers only to the part where you need a reference to a previous instance by specifying the name (assuming there is at most one node with the same name).

My suggestion is that you try out metaclasses. I know it's a controversial issue in Python but I think is worth knowing. Also I think there is a better and more pythonic way of doing this but nonetheless here is my solution.. The next code snippet will probably work. (not checked! I'm writing from my phone. Maybe small adjustments are required).

Class Metanode(object):
    __nodes = {}

def __new__(cls,name,val):
    if name not in Metanode.__nodes.keys():
        Metanode.__nodes[name] = object.__new__(cls,name,val)
    return Metanode.__nodes[name]

Then you add this as metaclasses:

class Node(metaclass=Metanode,object):
    ''' put rest of your def here '''
    pass

Now your metaclass hold a dictionary of instances. Whenever you create a new instance with the name 'x' you will get the last instance named with that name. Of course you also need to handle the destruction of these instances in the metaclass too (so the dictionary won't have keys to non-existing instances).

EDIT: After reviewing the code properly in my computer, this code doesn't work. However the next piece of code, not involving metaclasses at all will work (checked on my Ubuntu machine with python3):

class Node(object):
    nodes={}

    def new_init(self,name,val):
        self.name = name
        self.val = val
        self.children = [ ]

    def __new__(cls,name,val,*args,**kwds):
        if name not in Node.nodes.keys():
            Node.nodes[name] = super(Node,cls).__new__(cls,*args,**kwds)
            Node.nodes[name].new_init(name,val)
        return Node.nodes[name]

    def __init__(self,name,val):
        pass

    def sum_below(self):
        return self.val + sum(child.sum_below() for child in self.children)

    def add_child(self,node):
        if not isinstance(node,Node):
            '''raise-some-exception-or-whatnot'''
        self.children.append(node)

Answer 2

The problem why you are not getting same output with parent.sum_below() and Node(1, 100).sum_below() is that 'parent' is an object of Node class and has a child attribute containing another node object 'child' so it works the way it should but when you write Node(1, 100).sum_below() you are creating a new object with name attribute = 1 and value attribute = 100 and calling sub_below() method on it so, it will return the value of itself as it has no child added yet.

Moreover, you can't even access this newly created node later because you are not assigning it to any variable. To to that you should do something like this:

 >>>parent2 = Node(1, 100)
 >>>parent2.sum_below()
 100
 >>>parent2.add_child(parent1)
 >>>parent2.sum_below()
 400

Answer 3

The code seems ok. The only "imprefection" I see is that the special case:

if self.children == []: ...

is not needed at all. The simplified version:

def sum_below(self):
    ret = self.value
    for child in self.children:
        ret += child.sum_below()
    return ret

would work too. It could also be simplified further a bit by using sum:

def sum_below(self):
    return (self.value +
            sum(child.sum_below() for child in self.children))