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

Question

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?

I see a [mutable default argument](http://docs.python-guide.org/en/latest/writing/gotchas/#mutable-default-arguments) in `__init__`, and you never update the child's root in `add_child`. — user2357112, Jun 12 '16 at 18:37
Be very careful with `children=[]`. See http://stackoverflow.com/questions/366422/what-is-the-pythonic-way-to-avoid-default-parameters-that-are-empty-lists — P. Camilleri, Jun 12 '16 at 18:39
Thanks! I think i fixed that now with children=None, but it still blows up. — m fran, Jun 12 '16 at 18:41

Simon Kirsten · Accepted Answer · 2016-06-12T18:53:21.587

2

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)

edited Jun 12 '16 at 18:53

answered Jun 12 '16 at 18:42

Simon Kirsten

2,542
18
21

2

Use `if children is None` rather than `if not children` – P. Camilleri Jun 12 '16 at 18:44
2

still blows up, even using the fix suggested in the comment. – m fran Jun 12 '16 at 18:45
Doesn´t matter, does it? If `children` is `[]` it will still in both cases be `[]`, or am i wrong? – Simon Kirsten Jun 12 '16 at 18:45
1

Yes, but it makes your code clearer. You want to check if it is None, not if it evaluates to False. See http://stackoverflow.com/questions/7816363/if-a-vs-if-a-is-not-none : and read PEP8 on the matter. Also avoid spaces around = in default arguments (PEP8 again) – P. Camilleri Jun 12 '16 at 18:49
Okay, thank you. I do not normally use spaces around = but in this case I just edited OP's code. – Simon Kirsten Jun 12 '16 at 18:54

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

1 Answers1