Differences between 2 implementation of tree traversal

Viewed 48

In "Data Structures and Algorithms in Python" of Michael T. Goodrich, page 334, I've found the implementation of preorder traversal a little bit confusing.

def _subtree_preorder(self, p):
    """Generate a preorder iteration of positions in subtree rooted at p."""
    yield p                                         # visit p before its subtrees
    for c in self.children(p):                      # for each child c
        for other in self._subtree_preorder(c):     # do preorder of c’s subtree
            yield other                             # yielding each to our caller

I wonder why if there are any differences between the above implementation with:

def _subtree_preorder(self, p):
    yield p
    for c in self.children(p):
        yield from self._subtree_preorder(c)

The author just explained:

"because we are relying on generators rather than traditional functions, the recursion has a slightly different form. In order to yield all positions within the subtree of child c, we loop over the positions yielded by the recursive call self._subtree_preorder(c), and reyield each position in the outer context. Note that if p is a leaf, the for loop over self.children(p) is trivial (this is the base case for our recursion)."

I don't understand what he meant, can you help me?

Thanks

0 Answers
Related