Segmentation fault after the expected output in binary tree-CodePudding

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
   int number;
   struct node *left;
   struct node *right;
}
node;

void print_tree(node *root);
void free_tree(node *root);

int main(void)
{
   node *tree = NULL;

   node *n = malloc(sizeof(node));
   if (n == NULL)
   {
       return 1;
   }

   // root
   n->number = 2;
   n->left = NULL;
   n->right = NULL;

   tree = n;

   n = malloc(sizeof(node));
   if (n == NULL)
   {
       free_tree(tree);
       return 1;
   }

   n->number = 1;
   n->left = NULL;
   n->right = NULL;

   tree->left = n;

   n = malloc(sizeof(node));
   if (n == NULL)
   {
       free_tree(tree);
       return 1;
   }

   n->number = 3;
   n->left = NULL;
   n->right = NULL;

   tree->right = n;

   print_tree(tree);
   free_tree(tree);
   return 0;
}

void print_tree(node* root)
{
   if (root == NULL)
   {
       return;
   }
   print_tree(root->left);
   printf("%i\n", root->number);
   print_tree(root->right);
}

void free_tree(node* root)
{
   if (root == NULL)
   {
       return;
   }
   free_tree(root->left);
   free_tree(root->right);
   free_tree(root);
}

My code prints out the binary tree without any problem (1, 2 and 3 with new lines) but I also suffer from a segmentation fault.I've tried to see what causes this error and debug50 indicates that the error occurs in this line:

free_tree(root->left);

I don't really understand why would this line cause a segmentation fault.I would appreciate the help.

CodePudding user response：

Let's take a look at your free_tree function, which I'm guessing is for freeing up the memory allocated for the tree.

void free_tree(node* root)
{
   if (root == NULL)
   {
       return;
   }
   //some omitted code
   free_tree(root);
}

Do you see the issue? If root is not null, the recursion repeats infinitely. This actually causes a segmentation fault as each layer of recursion allocates more memory on the stack, until there is no more memory left and a segmentation fault is thrown.

I think you were trying to write free(root) instead of free_tree(root). This change would prevent the segmentation fault while following the original logic of your code.

Note that in most cases, you don't even need to run free_tree at all, as this is only being run once (before your code terminates) and most modern operating systems will free the memory for you anyway.

CodePudding user response：

Free tree does not free memory allocated with malloc. free_tree() is called until it runs out of stack space.

Do this instead:

void free_tree(node* root) {
   printf("free_tree()\n");
   if (root == NULL) {
       return;
   }

   if (root->left != NULL) {
       free_tree(root->left);
   }
   if (root->right != NULL) {
       free_tree(root->right);
   }
   printf("do free\n");
   free(root);
   root=NULL;
}

To assist with debugging, add a printf("malloc\n") after each malloc. Make sure when you run, you see the same number of malloc()'s as free()'s