How to delete elements in a binary tree in C?

Question

I'm trying to understand the deletion of nodes in a binary tree. This is the code snippet that I found from the tutorial which explains the same.

The node looks like this:

struct node
{
  int key_value;
  struct node *left;
  struct node *right;
};

Source : http://www.cprogramming.com/tutorial/c/lesson18.html

    void destroy_tree(struct node *leaf)
    {
      if( leaf != 0 )
      {
          destroy_tree(leaf->left);
          destroy_tree(leaf->right);
          free( leaf );
      }
    }

My doubt is regarding the free(leaf) part. I mean, the author claims that this will recursively delete all the nodes starting from the bottom left most one. But isn't free(leaf) just freeing the memory of the leaf pointer? Aren't all the nodes still connected? How does the clearing take place?

Answer 1

I'm showing you graphically how would tree change:

START:

                  10
               /      \
              6        14
             / \       /  \
            free 8    11    18

                  10
               /      \
              6           14
             /   \       /  \
            free free  11    18


                  10
               /       \
              free        14
             /   \       /  \
            free  free  11  18


                   10
                /       \
              free         14
             /   \       /    \
            free  free  free  18

                   10
                 /       \
              free         14
             /   \       /     \
            free  free  free  free

                     10
                 /       \
              free         free
             /   \       /     \
            free  free  free  free

                    free
                 /       \
              free         free
             /   \       /     \
            free  free  free  free

Of course in the end, nodes are not connected, they no longer exist. I just showed in picture how would they change during the course of this algorithm. If you have any further questions, feel free to ask.

I strongly suggest you that, whenever you can't understand how tree recursion work, on piece of paper write a picture and then go trough algorithm like I wrote above.