Node with as many children as possible python

Question

I want to create a data structure in Python, but since I'm very C oriented. I need a little bit of help.

In general, I want to create a Node class which will contain the data, a pointer to a sibling, pointers to the children and a pointer to the parent.

this is a way to think of the Node class:

                                 NODE
            /            /         ...  \                   \
       child_node1 - child_node2 - ... - child_node(N-1) - child_nodeN

What I'm struggling with so far is: I want to overload the '+' operator for the Node class so I can do this:

node1 = Node("data1")
node2 = Node("data2", 3)
node1 = node1 + node2

So basically make the 2 nodes, siblings.

Here's my code:

class Node:
def __init__(self, data = None, numberOfChildren = 0):
    '''
    Creates a new Node with *numberOfChildren* children. 
    By default it will be set to 0, meaning it will only create the root of the tree.
    No children whatsoever.
    '''
    self.__sibling_count = 0
    self.__parent = Node()
    self.__sibling = Node()
    self.__data = data

    self.__children = []
    if numberOfChildren != 0:
        '''
        The Node has children and we need to initialize them
        '''
        for i in range(numberOfChildren):
            self.__children[i] = Node()

def getParent(self):
    return self.__parent


def getData(self):
    return self.__data

def getChild(self, i):
    '''
    Returns the ith child of the current *Node*.
    '''
    return self.__children[i]


def __add__(self, other):
    '''
    Overloads the *+* function so that *Node* objects can be added.
    The 2 merged *Node* elements will now be siblings.
    ex. node1  = Node()
        node2 = Node()
        node1 = node1 + node2
    '''
    if self.__sibling_count == 0:
        self.__sibling = other
        self.__sibling_count += 1
    return self

But when I try to add 2 nodes like this:

node1 = Node()
node2 = Node()
node1 = node1 + node2

I get a RuntimeError: maximum recursion depth exceeded. Why is this happening?

Answer 1

Operator overriding in Python is allowed, but using the + operator for something that is not concatenation or summing is frowned upon. A more pythonic implementation would be something like this untested fragment:

class Node(object):
    def __init__(self, parent=None):
        self.set_parent(parent)
        self.children = set()

    def set_parent(self, parent):
        if self.parent and self.parent is not parent:
            self.parent.children.remove(self)
        self.parent = parent

    def siblings(self):
        if self.parent is None:
            return []
        return [_ for _ in self.parent.children if _ is not self]

    def add_child(self, node):
        self.children.add(node)
        node.set_parent(self)

    def add_sibling(self, node):
        assert self.parent, "root node can't have siblings"
        self.parent.add_child(node)

... and so on. Off course you can override the + operator to perform add_sibling, but the gist of it is to rely heavily on the native collections.

If you want to create a note with 3 children, it would be:

root = Node()
nodes = [Node(parent=root) for _ in range(3)]

Answer 2

Python recursion is limited to prevent stack overflowing and infinite recursion. There for recursion without break conditions or counter will be stopped after some-many iterations.

Stop creating any more nodes after a number of levels, otherwise python will stop you. You are activating __init_ in the first Node, then in every one of it's children and so on. This never stops, and trigger this run-time error.

See that as an estimation to how far you can go:

>>> def f(): f()
>>> f()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in f
  File "<stdin>", line 1, in f
  File "<stdin>", line 1, in f
  ... another 995 times the same
  File "<stdin>", line 1, in f
RecursionError: maximum recursion depth exceeded

You can change __init__ to this:

def __init__(self, levels = 5, numberOfChildren = 0, data = None):
    '''
    Creates a new Node with *numberOfChildren* children. 
    By default it will be set to 0, meaning it will only create the root of the tree.
    No children whatsoever.
    '''
    self.__sibling_count = 0
    # these will only produce **new** nodes. I commented them.
    # self.__parent = Node()
    # self.__sibling = Node()
    self.__data = data

    self.__children = []
    if numberOfChildren != 0 and levels > 0:
        '''
        The Node has children and we need to initialize them
        '''
        for i in range(numberOfChildren):
            self.__children[i] = Node(levels - 1, numberOfChildren)