Set an element of an array of *char as NULL in C

Question

I have the task of going through a binary search tree and collecting the keys in every node and storing them in an array. After this, I have to set the last element of this array as NULL. This is all done inside a function, which then returns this array of *char.

I believe the part about collecting the keys and storing them in the array is working well, as I've tested that enough. However, I'm not able to define the last element of the array as NULL correctly. I thought it should be done like this:

list_keys[tree_size(tree)] = NULL;

However, after some printf's, I realized that this was cleaning my tree. When I print tree_size(tree) before this line, it gives me the size of the tree correctly. However, when I do it after that line, it gives me 0. I don't believe that the problem is in the function tree_size() because when I attempt to access an element of the tree before that line, it works well, but after the line, I get a Segmentation fault (core dumped) error, probably due to trying access something that doesn't exist anymore.

I have no idea what's wrong, so any help is appreciated. Thanks in advance.

EDIT:

The tree is of the type tree_t and it's defined as:

struct tree_t {
    struct entry_t *entry;
    struct tree_t *right_child;
    struct tree_t *left_child;
};

The tree_size() is defined as:

int tree_size(struct tree_t *tree) {
    if (tree->entry != NULL) {
        //if two children exist
        if (tree->left_child != NULL && tree->right_child != NULL) {
            return 1 + tree_size(tree->left_child) + tree_size(tree->right_child);
        }
        //there's a right child and there isnt a left child
        if (tree->right_child != NULL && tree->left_child == NULL) {
            return 1 + tree_size(tree->right_child);
        }
        //there's a left child and there isnt a right child
        if (tree->left_child != NULL && tree->right_child == NULL) {
            return 1 + tree_size(tree->left_child);
        }
        //there are no children
        if (tree->left_child == NULL && tree->right_child == NULL) {
            return 1;
        }
      }
    //if the entry is empty
    return 0;
}

Basically, what I'm doing right now is:

First, I define list_keys and allocate memory:

char **list_keys;
list_keys = (char *)malloc((tree_size(tree)+1)*sizeof(char));

Then, I call an auxiliary function tree_get_keys_aux(tree, list_keys, 0) that will do the initial part I mentioned. It is defined as:

void tree_get_keys_aux(struct tree_t *tree, char **list_keys, int index) {
  //N
  list_keys[index] = (char *)malloc((strlen(tree->entry->key))*sizeof(char)); //allocating memory for each string that I want to add to the list
  strcpy(list_keys[index],tree->entry->key); //copying the content

  index = index + 1;

  //L
  if (tree->left_child != NULL) {
    tree_get_keys_aux(tree->left_child, list_keys, index);
  }

  //R
  if (tree->right_child != NULL) {
    tree_get_keys_aux(tree->right_child, list_keys, index);
  }

  return;

}

Then, I do the line that's bringing me problems,

list_keys[tree_size(tree)] = NULL;

And lastly,

return list_keys;

We don't know how you are implementing the tree. Please post a [Minimal, Reproducible Example](https://stackoverflow.com/help/minimal-reproducible-example). — MikeCAT, Oct 22 '20 at 15:20
*"I don't believe that the problem is in the function tree_size()"* - and then you add that function? Why? Where do you believe the error is? Please, post a [mre]. — Marco Bonelli, Oct 22 '20 at 15:36
Your `tree_size()` function can be simplified a lot by allowing it to recurse with the null pointers: `int tree_size(struct tree_t *tree) { if (tree->entry != NULL) return 1 + tree_size(tree->left_child) + tree_size(tree->right_child); return 0; }` — Ian Abbott, Oct 22 '20 at 15:39
@IanAbbott You have to check if `tree` is not `NULL` for that. — MikeCAT, Oct 22 '20 at 15:39
@MikeCAT Yes, good point! So change it to `if (tree != NULL && tree->entry != NULL) ...`. — Ian Abbott, Oct 22 '20 at 15:41
Is it possible to have a tree node with `entry` null, but `left_child` and/or `right_child` non-null? — Ian Abbott, Oct 22 '20 at 15:45
@MarcoBonelli I can't figure out what's wrong and, even though I believe that function is working properly, something could've slipped my attention and the problem could indeed be there. I just wanted to provide as much information as I have. — maf, Oct 22 '20 at 15:55
@IanAbbott The exercise I'm doing isn't very clear about that. I think it is possible but it's not going to happen. — maf, Oct 22 '20 at 15:59
1. You don't allocated for terminating null-characters and you have to allocate for that. 2. `tree_get_keys_aux` won't recognize the number of data for left child and they may be overwritten in by data from the right child. — MikeCAT, Oct 22 '20 at 16:02

MikeCAT · Accepted Answer · 2020-10-23T13:09:44.170

Firstly,

list_keys = (char *)malloc((tree_size(tree)+1)*sizeof(char));

is wrong. The elements are char*, so you have to allocate for that or you will cause out-of-range access.

It should be:

list_keys = malloc((tree_size(tree)+1)*sizeof(char*));

or

list_keys = malloc((tree_size(tree)+1)*sizeof(*list_keys));

See also: c - Do I cast the result of malloc? - Stack Overflow

Secondly,

  list_keys[index] = (char *)malloc((strlen(tree->entry->key))*sizeof(char)); //allocating memory for each string that I want to add to the list
  strcpy(list_keys[index],tree->entry->key); //copying the content

is wrong. You have to allocate one more element for terminating null-character.

It should be:

  list_keys[index] = malloc((strlen(tree->entry->key) + 1)*sizeof(char)); //allocating memory for each string that I want to add to the list
  strcpy(list_keys[index],tree->entry->key); //copying the content

Thirdly, tree_get_keys_aux is not recoginizing number of elements in left child and data from left child will be overwritten by data from right child. To avoid this overwriting, you can use tree_size to determint the tree size and advance index according to that.

  //L
  if (tree->left_child != NULL) {
    tree_get_keys_aux(tree->left_child, list_keys, index);
    index += tree_size(tree->left_child); // add this
  }

  //R
  if (tree->right_child != NULL) {
    tree_get_keys_aux(tree->right_child, list_keys, index);
  }

Nice usage of `list_keys = malloc((tree_size(tree)+1)*sizeof(*list_keys));` — chux - Reinstate Monica, Oct 22 '20 at 16:52
Thank you so much! Your suggestions really helped!! I only had to add `if (tree-> left_child != NULL)` before increasing the index and now it works perfectly. — maf, Oct 23 '20 at 10:45

Set an element of an array of *char as NULL in C

1 Answers1