Binary Tree Traversal - Preorder - visit to parent
<p>I'm trying to understand the recursive implementation of preorder traversal as shown in this link <a href="http://interactivepython.org/runestone/static/pythonds/Trees/TreeTraversals.html" rel="nofollow">http://interactivepython.org/runestone/static/pythonds/Trees/TreeTraversals.html</a></p>

<pre><code>def preorder(tree): 
    if tree:  
        print(tree.getRootVal())  
        preorder(tree.getLefChild())  
        preorder(tree.getRightChild())   
</code></pre>

<p>I understand how pre-order works, however what I'm flustered with is the recursive implementation shown above.  I still can't figure out how after traversing through all the left children the algorithm goes back to the nearest ancestor(parent). I've tried working this out on paper but it still doesn't click. </p>

<p><code>preorder(tree.getLefChild())</code> goes through all the left children for the current tree. That method then returns, just like all other methods, then continues on with the parent's right children. </p>

<p>A quick visualization </p>

<pre><code>def preorder(tree): 
    if tree:  
        print(tree.getRootVal())  
        preorder(tree.getLefChild())  # Expand this
        preorder(tree.getRightChild())  
</code></pre>

<p>Becomes...</p>

<pre><code>def preorder(tree): 
    if tree:  
        print(tree.getRootVal())  
        # Entering recursion ... 
        if (tree.getLefChild()):
            print(tree.getLefChild().getRootVal())  
            preorder(tree.getLefChild().getLefChild())  # And so on...            
            preorder(tree.getLefChild().getRightChild())  
        # Exiting recursion...
        preorder(tree.getRightChild())  
</code></pre>

python recursion binary-tree