0

I'm going through "Chapter 8: Trees" in the book "Data Structures in Python" by Michael Goodrich and I have difficulty understanding the following recursion for tree traversal.

def preorder(self):
        if not self.is_empty():
            for p in self._subtree_preorder(self.root()):
                yield p

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

Both of these functions are inside a LinkedBinaryTree ADT, and the function T.children(p) returns the children of a node p in tree T. Can someone help me understand what the yield other does? Does it yield subtree to be re-yielded by yield p or does it actually yield a node? My recursion skills is pretty bad so I don't really understand how this works. Do you have any resources where I can learn more about different types of recursion? Thank you in advance!

Jake Nguyen
  • 61
  • 7
  • 1
    What is `_subtree_preorder` supposed to yield _as a result_? Presumably, individual nodes. What is `other`? Something yielded from a call to `_subtree_preorder`. `_subtree_preorder` yields nodes, thus `other` is also a node. You could replace that inner loop with `yield from self._subtree_preorder(c)`, BTW. – ForceBru Aug 12 '20 at 19:54
  • @ForceBru so ```other``` is yielded by the inner loop to be yielded by the call ```yield p``` right? I tried to draw the stack-frame for this recursion but I don't really know how. I've only been exposed to simpler recursion. @ggorlen Unfortunately, no. But thank you for your help! :) – Jake Nguyen Aug 12 '20 at 20:08

0 Answers0