m fran m fran - 5 months ago 26
Python Question

this python code for pretty printing a tree blows up with a stack overflow

I cannot figure out why this explodes and I'm still trying to learn python debugging.

class Node():
def __init__(self, parent = None, children = [], data = None):
self.parent = parent
self.children = children
self.data = data
if parent == None:
self.root = self
else:
self.root = self.parent.root

def add_child(self, child):
self.children.append(child)
child.parent = self


def is_root(self):
return self.root == self

def is_leaf(self):
return self.children == []

def is_empty(self):
return self.data == None

def pprint(self):
def _pprint(ast, l):
if not self.is_empty():
print(l * " ", self.data)
if not self.is_leaf():
for child in self.children:
_pprint(child, l + 1)

_pprint(self, 0)


I use the code this way:

root = Node()
root.add_child(Node(data="a"))
root.pprint()


after a while, the pprint method gives an exception:

...
File "ll.py", line 56, in _pprint
_pprint(child, l + 1)
File "ll.py", line 56, in _pprint
_pprint(child, l + 1)
File "ll.py", line 56, in _pprint
_pprint(child, l + 1)
File "ll.py", line 56, in _pprint
_pprint(child, l + 1)
File "ll.py", line 52, in _pprint
if not self.is_empty():
File "ll.py", line 48, in is_empty
return self.data == None
RecursionError: maximum recursion depth exceeded in comparison


the "base case" should be, i think, the leaf nodes, with no children. What am I missing?

Answer
def __init__(self, parent = None, children = [], data = None):

All Nodes will use the same mutable object children. This results in children acting like a global variable.

Read more here.

Possible workaround:

def __init__(self, parent = None, children = None, data = None):
    if not children:
        self.children = []
    else:
        self.children = children

Edit:

Also, of course you wanted to write ast instead of self in the _pprint function:

def _pprint(ast, l):
    if not ast.is_empty():
        print(l * " ", ast.data)

    if not ast.is_leaf():
        for child in ast.children:
            _pprint(child, l + 1)
Comments