Python: Tree Recursion Issue

Question

I have an issue with processing a tree correctly. The tree is simple, just a node and list of children

class Tree (object):
    __slots__ = "node","children"
    def __init__(self,node,children=[]):
        self.node = node
        self.children = children

Using a linearization technique, though, we are supposed to detect how many (sub)trees a given branch ends. For example, if we construct a tree like so:

t = Tree(1, [Tree(2, [Tree(5), Tree(3, [Tree(4)])])])

then t.linearize() should output 1 2 5 NIL 3 4 NIL NIL NIL NIL. Each NIL represents 1 (sub)tree being ended.

My current version only output the following: 1 2 5 NIL 3 4 NIL, without the multiple NILs. Any idea what I'm leaving out?

def linearize(self):
    print self.node,
    if self.children == []:
        print "NIL",
    for child in self.children:
        child.linearize()

Generally speaking, using `children=[]` as a default is a bad idea... See http://stackoverflow.com/questions/1132941/least-astonishment-in-python-the-mutable-default-argument — mgilson, Feb 04 '13 at 18:51

score 1 · Accepted Answer · answered Feb 04 '13 at 18:54

IIUC you really want:

def linearize(self):
    print self.node,
    for child in self.children:
        child.linearize()
    print "NIL",

which gives:

In [5]: t.linearize()
1 2 5 NIL 3 4 NIL NIL NIL NIL

Right now, you don't print "NIL" when there are children. (And as noted in the comments, you really want children=None and then self.children = children if children is not None else [] or something.)

You might also be interested in reworking this to yield each element, rather than merely printing them, but obviously that's up to you.

Python: Tree Recursion Issue

1 Answers1