title: recursive delete on a binary tree
body: <p>I am trying to understand how the recursive method of deletion of a binary search tree works. The code that I came across in many places looks as follows:</p>
  
  <pre><code>void destroy_tree(struct node *leaf)
  {
    if( leaf != 0 )
    {
        destroy_tree(leaf-&gt;left);
        destroy_tree(leaf-&gt;right);
        free( leaf );
    }
  }
  </code></pre>
  
  <p>I can't understand however a) how does it work if there are no returns in the routine? b) when free() gets to be called? I think about, e.g., such a tree:</p>
  
  <pre><code>                           10
                           /    \
                          6      14
                         / \    /  \
                        5   8  11  18
  </code></pre>
  
  <p>So my understanding is that I traverse 10->6->5, and then I call destroy_tree(5->left). Therefore, leaf inside if is NULL, and what is if-dependent is not executed, hence 5 is not being deleted. Where do I make mistake in this reasoning? How does winding and unwinding work here? Any help kindly appreciated :-)</p>