title: Deleting a binary tree using inorder traversal
body: <p>I was learning how to delete a binary tree using Postorder traversal. I understand that to delete a node, first we need to delete its child node and then the node itself, so Postorder traversal is the best fit to delete a binary tree. I thought of doing the same using Inorder traversal, everything works fine but I don't understand how the below code works?<br></p>
  
  <pre><code>#include&lt;stdio.h&gt;
  #include&lt;malloc.h&gt;
  
  struct b_tree{
      int data;
      struct b_tree *left,*right;
  };
  
  typedef struct b_tree tree;
  
  tree* create_node(int data)
  {
      struct b_tree* new_node=(tree*)malloc(sizeof(tree));
      new_node-&gt;data=data;
      new_node-&gt;left=NULL;
      new_node-&gt;right=NULL;
      return new_node;
  }
  
  void delete_tree(tree *root)
  {
      if(root==NULL)
          return;
      delete_tree(root-&gt;left);
      printf("Deleting %d node.\n",root-&gt;data);
      free(root);
      delete_tree(root-&gt;right);
  }
  
  int main()
  {
      tree *root=NULL;
      root=create_node(1);
      root-&gt;left=create_node(2);
      root-&gt;right=create_node(3);
      root-&gt;left-&gt;left=create_node(4);
      root-&gt;left-&gt;right=create_node(5);
      root-&gt;left-&gt;right-&gt;left=create_node(6);
      root-&gt;left-&gt;right-&gt;right=create_node(7);
      root-&gt;right-&gt;right=create_node(8);
      root-&gt;right-&gt;right-&gt;left=create_node(9);
      delete_tree(root);
      root=NULL;
      return 0;
  }
  </code></pre>
  
  <p><a href="https://i.stack.imgur.com/MbHU2.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/MbHU2.jpg" alt="Tree"></a><br>
  <strong>According to Inorder traversal first node to be deleted is <code>4</code> and after that <code>2</code>, but once we freed <code>2</code> it should loose all it's data, means it should not retain the pointer to right node as well which is <code>5</code>, but even after <code>2</code> is freed its left child <code>5</code> is still traversed but it should not happen because node <code>2</code> is already freed.<br> <br></strong>
  The output of the above code is:<br>
  <a href="https://i.stack.imgur.com/pFIcD.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/pFIcD.jpg" alt="Output"></a><br><br>
  I was expecting the output to be in the following order of nodes: <code>4 2 1</code>.<br><br>
  I don't understand how all this is working. Please correct me if I'm wrong.</p>