Yield all full root-leaf paths through tree structure in Python

Question

I'm trying to adapt this answer in two ways:

I want to make the traverse function a class method, and
I want a call to traverse to yield the list of all root-to-leaf paths (list of lists) in the tree

First change was trivial, second one I'm struggling with. Here's my class definition:

class createnode:
    """ thanks to https://stackoverflow.com/a/51911296/1870832"""
    def __init__(self,nodeid):
        self.nodeid=nodeid
        self.child=[]

    def __str__(self):
        print(f"{self.nodeid}")

    def traverse(self, path = []):
        path.append(self.nodeid)
        if len(self.child) == 0:
            #print(path)
            yield path
            path.pop()
        else:
            for child in self.child:
                child.traverse(path)
            path.pop()

I construct a tree with:

ROOT_NODE = 0
root = createnode(ROOT_NODE)
lvl1 = [createnode(1), createnode(2), createnode(3)]
root.child += lvl1

root.child[0].child += [createnode(4), createnode(5)]
root.child[1].child += [createnode(6), createnode(7)]
root.child[2].child += [createnode(8), createnode(9)]

Desired output for printing all full root-leaf paths (e.g. w/ code below)

paths = root.traverse()
for p in paths:
    print(p)

is:

[0, 1, 4]
[0, 1, 5]
[0, 2, 6]
[0, 2, 7]
[0, 3, 8]
[0, 3, 9]

I'd suggest a more stringent test case - with greater tree depth. — dstromberg, Mar 20 '20 at 17:32
I get the error: `AttributeError: 'int' object has no attribute 'traverse'` for the line: `child.traverse(path)` — quamrana, Mar 20 '20 at 17:32
sorry quamrana I should have used `children = [createnode(32), createnode(5)]`, this `children...` statement was a more complicated list comprehension before and I accidentally over-simplified it for this question — Max Power, Mar 20 '20 at 18:03

score 2 · Accepted Answer · answered Mar 20 '20 at 17:41

You need to look into a recursive generator.

I have corrected your setup code:

class createnode:
    """ thanks to https://stackoverflow.com/a/51911296/1870832"""
    def __init__(self,nodeid):
        self.nodeid=nodeid
        self.child=[]

    def __str__(self):
        print(f"{self.nodeid}")

    def traverse(self, path = None):
        if path is None:
            path = []
        path.append(self.nodeid)
        if len(self.child) == 0:
            yield path
            path.pop()
        else:
            for child in self.child:
                yield from child.traverse(path)
            path.pop()

ROOT_NODE = 0
root = createnode(ROOT_NODE)
children = [createnode(32), createnode(5)]

root.child += children

paths = root.traverse()
for p in paths:
    print(p)

Output:

[0, 32]
[0, 5]

confirmed gives all full paths on updated larger test case. thanks again! just trying to wrap my head around `yield from` now, I hadn't even realized that exists. starting here: https://stackoverflow.com/a/26109157/1870832 — Max Power, Mar 20 '20 at 18:52

Alistair · Answer 2 · 2020-03-20T19:07:53.727

1

I don't have any experience with yield yet but I'd do it like this:

class createnode:
    """ thanks to https://stackoverflow.com/a/51911296/1870832"""
    def __init__(self,nodeid):
        self.nodeid=nodeid
        self.child=[]

    def __str__(self):
        print(f"{self.nodeid}")

    def traverse(self, path = []):
        path.append(self.nodeid)
        if len(self.child) == 0:
            print(path)
            path.pop()
        else:
            for child in self.child:
                child.traverse(path)
            path.pop()
ROOT_NODE = 0
root = createnode(ROOT_NODE)
lvl1 = [createnode(1), createnode(2), createnode(3)]
root.child += lvl1

root.child[0].child += [createnode(4), createnode(5)]
root.child[1].child += [createnode(6), createnode(7)]
root.child[2].child += [createnode(8), createnode(9)]

root.traverse()

[0, 1, 4]

[0, 1, 5]

[0, 2, 6]

[0, 2, 7]

[0, 3, 8]

[0, 3, 9]

edited Mar 20 '20 at 19:07

answered Mar 20 '20 at 18:10

Alistair

589
3
11

Hey I really like this solution (+1), I originally tried with `return` instead of `yield` but messed it up and came to think it required `yield.` This doesn't give my desired outcome on trees of depth 3 though. I think this is my fault for not specifying a good enough test case as @dstromberg suggested. Updating my question now... – Max Power Mar 20 '20 at 18:25
updated question to reflect desired root-to-leaf paths only and with new better test case – Max Power Mar 20 '20 at 18:32
your solution still works in the new case if you just call print and only call traverse once, see changes – Alistair Mar 20 '20 at 19:09
so now you're printing each path one at a time, but not returning to a function caller a list of all full paths. I think that's what's difficult to do without yield? The question I originally mentioned that I was trying to modify already will print all the unique paths. But I'm trying to get a 2d list of list (or a generator of lists) back from a call to traverse – Max Power Mar 20 '20 at 19:18
1

I see, having tried to do it without using yield, it's definitely tough. I could do with researching yield myself – Alistair Mar 20 '20 at 19:30

Yield all full root-leaf paths through tree structure in Python

2 Answers2