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 stackoverflow.com/questions/1132941/… — mgilson
– mgilson, Commented Feb 4, 2013 at 18:51

DSM · Accepted Answer · 2013-02-04 18:54:50Z

1

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.

answered Feb 4, 2013 at 18:54

DSM

355k67 gold badges606 silver badges504 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Python: Tree Recursion Issue

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related