CODEWITHSUNDEEP
pythonrecursiontree
Adam_G
Adam_G

Reputation: 7879

Python: Tree Recursion Issue

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()

Upvotes: 0

Views: 561

Answers (1)

DSM
DSM

Reputation: 353479

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.

Upvotes: 1

Related Questions