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.
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.
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With