Python (yield): all paths from leaves to root in a tree

5
votes

I want to generate all paths from every leaf to root in a tree. I'd like to do that with generators, to save memory (tree can be big). Here's my code:

def paths(self, acc=[]):
    if self.is_leaf():
        yield [self.node]+acc

    for child in self.children:
        child.paths([self.node]+acc)

But it doesn't work. Why? Invoked at root, it traverses the tree from top to bottom, collecting nodes in "acc". "acc" should be returned in every leaf...

is_leaf() is true if self.children is empty.

2
pythonyield

2 Answers

7
votes

This code only yields leaves that are (immediate) children of the root. The other ones get visited, they yield to the upper function, but the upper function does nothing with them. What you need is to yield them from the lower function to the upper one:

def paths(self, acc=[]):
    if self.is_leaf():
        yield [self.node]+acc

    for child in self.children:
        for leaf_path in child.paths([self.node]+acc): # these two
            yield leaf_path                            # lines do that

This should do the trick.

1
votes

At the moment the for loop doesn't yield anything. It should instead yield all the elements that are generated by the recursive call:

for child in self.children:
    for path in child.paths([self.node]+acc):
        yield path