How this Python generators based inorder traversal method works
<p>I am quite new to python and still exploring. Came across generators and below code snippet implementing inorder binary tree traversal using generators:</p>

<pre><code>def inorder(t):
    if t:
        for x in inorder(t.left):
            yield x

        yield t.label

        for x in inorder(t.right):
            yield x
</code></pre>

<p>Now I know following fact about generators: they remember the local variable values across calls. However this function is recursive. So how it remembers local variable values across these different recursive calls? </p>

<p>Also it was easy to understand normal recursive inorder program (not involving generators) as there were clear recursion termination conditions explicitly specified. But how this recursion with generators works?</p>

<p>I modified the code somewhat to get the idea of the flow of the execution sequence. Basically I added some <code>print()</code> statements.</p>

<pre><code>class BinaryTreeNode():
    def __init__(self, pLeft, pRight, pValue):
        self.left = pLeft
        self.right = pRight
        self.label = pValue

def inorder(t):
    print("at the beginning of inorder(t): " + (str(t.label) if t else "None" ))
    if t:
        for x in inorder(t.left):
            print("inside inorder(t.left):" + str(t.label))   #delete
            yield x

        print("inside inorder(t):" + str(t.label))   #delete
        yield t.label

        for x in inorder(t.right):
            print("inside inorder(t.right):" + str(t.label))  #delete
            yield x

node1 = BinaryTreeNode(None,None,1)
node3 = BinaryTreeNode(None,None,3)
node2 = BinaryTreeNode(node1,node3,2)
node5 = BinaryTreeNode(None,None,5)
node4 = BinaryTreeNode(node2,node5,4)

root = node4

for i in inorder(root):
    print(i)
</code></pre>

<p>The output is:</p>

<pre><code>1    at the beginning of inorder(t): 4
2    at the beginning of inorder(t): 2
3    at the beginning of inorder(t): 1
4    at the beginning of inorder(t): None
5    inside inorder(t):1
6    inside inorder(t.left):2
7    inside inorder(t.left):4
8    1
9    at the beginning of inorder(t): None
10    inside inorder(t):2
11    inside inorder(t.left):4
12    2
13    at the beginning of inorder(t): 3
14    at the beginning of inorder(t): None
15    inside inorder(t):3
16    inside inorder(t.right):2
17    inside inorder(t.left):4
18    3
19    at the beginning of inorder(t): None
20    inside inorder(t):4
21    4
22    at the beginning of inorder(t): 5
23    at the beginning of inorder(t): None
24    inside inorder(t):5
25    inside inorder(t.right):4
26    5
27    at the beginning of inorder(t): None
</code></pre>

<p>Notice that second call to <code>inorder(node4)</code> didnt print <code>at the beginning of inorder(t): 4</code> but it printed <code>at the beginning of inorder(t): None</code> (line 9 in output). That means generators also remembers the last executed line (mostly because it remembers program counter value in the last call).</p>

<p>Also every for loop obtains generator instance from the function <code>inorder()</code>. This generator is specific to for loop and hence there local scope is maintained separately.</p>

<p>Above traverses this tree:</p>

<pre><code>    4
   / \
  2   5
 / \
1   3
</code></pre>

<p>Also the termination occurs when each of the recursive calls reach to its end. This result in following recursive call tree:</p>

<pre><code>==&gt;inorder(&lt;4&gt;) 
   |---&gt; x in inorder(left&lt;2&gt;)
                 |---&gt; x in inorder(left&lt;1&gt;)
                               |---&gt; x in inorder(left&lt;None&gt;) --&gt; terminate
                                    yield 1   (note the indention, it is not yield inside first for-in loop but after it)
                            yield 1  (note the indentation, this is yield inside first for-in loop)
              yield 1



inorder(&lt;4&gt;)
   |---&gt; x in inorder(left&lt;2&gt;)
                 |---&gt; x in inorder(left&lt;1&gt;)        
==============================&gt;|---&gt; x in inorder(right&lt;None&gt;) --&gt; terminate
                      yield 2
              yield 2



inorder(&lt;4&gt;)
   |---&gt; x in inorder(left&lt;2&gt;)
================&gt;|---&gt; x in inorder(right&lt;3&gt;)                                                      
                               |---&gt; x in inorder(left&lt;None&gt;) --&gt; terminate
                                     yield 3  
                            yield 3
              yield 3     



inorder(&lt;4&gt;)
  |---&gt; x in inorder(left&lt;2&gt;)
                |---&gt; x in inorder(left&lt;1&gt;)        
=============================&gt;|---&gt; x in inorder(right&lt;None&gt;) --&gt; terminate
                      terminate
             terminate
        yield 4



inorder(4)
==&gt;|---&gt; x in inorder(right&lt;5&gt;)
                 |---&gt; x in inorder(left&lt;None&gt;) --&gt; terminate
                       yield 5 
              yield 5


inorder(4)
   |---&gt; x in inorder(right&lt;5&gt;)                 
===============&gt;|---&gt; x in inorder(right&lt;None&gt;) --&gt; terminate
                      terminate
              terminate
         terminate
</code></pre>

<p>(explaination:</p>

<ul>
<li><code>&lt;i&gt;</code> means call with <code>nodei</code> as parameter</li>
<li><code>left&lt;i&gt;</code> represents <code>inorder(t.left)</code> call inside first <code>for-in</code> loop where <code>t.left</code> is <code>nodei</code></li>
<li><code>right&lt;i&gt;</code> represents <code>inorder(t.right)</code> call inside second <code>for-in</code> loop where <code>t.right</code> is <code>nodei</code></li>
<li><code>===&gt;</code> shows where execution begins in that particular call)</li>
</ul>

python