What's wrong with my realloc doing on 2d-array

Question

I am solving binary tree paths leet code programming question 257. I am having issue for one of the larger input where my code is getting segmentation fault. I suspect that there is an problem with my realloc but I am not able to figure it out.

Below is my approach:

Initially I started by dynamically allocating 80 bytes of memory of type char (80/8 = 10 rows)and storing the returned address to char **res variable.

char ** res = (char **)malloc(sizeof(char *) * sum);

I am calling findpath function recursively to find all the binary tree paths. Whenever one path is found , I dynamic allocate 100 bytes for each row index.

res[resIdx] = (char *)malloc(sizeof(char) * 100);

I have one global variable resIdx which points to the current row index where I copy the found binary tree path and increment the global variable resIdx.

if the resIdx becomes greater then total number of rows which was previously allocated then I do realloc of the memory but it looks like realloc is getting failed.

    if (resIdx >= sum)
    {
       sum = sum + 10;
       res = (char **)realloc(res,sizeof(char *) * sum);  //Any issue here?
    }

Can anyone please help me to figure out what's wrong I am doing in my code. Below is my full code

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     struct TreeNode *left;
*     struct TreeNode *right;
* };
*/


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

int sum;
int resIdx;
void findpath (struct TreeNode* root, int *ls,int ls_idx,char **res);
char ** binaryTreePaths(struct TreeNode* root, int* returnSize){

    if (root == NULL)
    {
        *returnSize = 0;
        return NULL;
    }
    resIdx = 0;
    sum = 10;
    char ** res = (char **)malloc(sizeof(char *) * sum);
    int ls[100];
    findpath(root,&ls[0],0,res);
    *returnSize = resIdx;
    return &res[0];

}


void findpath (struct TreeNode* root, int *ls,int ls_idx,char **res)
{
    char temp[100];
    int l=0,i=0;
    if (root->left == NULL && root->right == NULL)
    {
        ls[ls_idx] = root->val;
        ls_idx+=1;
        if (resIdx >= sum)
        {
           sum = sum + 10;
           res = (char **)realloc(res,sizeof(char *) * sum);
        }
  
        res[resIdx] = (char *)malloc(sizeof(char) * 100);
        while (i < ls_idx)
        {
            if (i==0)
            {
                l = l + sprintf(&temp[l], "%d", ls[i]);

            }
            else
            {
                l = l + sprintf(&temp[l], "->%d", ls[i]);
            }
            i++;
        }
        strcpy(res[resIdx],temp);
        resIdx++;
        return; 
    }  
    ls[ls_idx] = root->val;
    if (root->left != NULL)
    {
        findpath(root->left,ls,ls_idx+1,res);   
    }

    if (root->right != NULL)
    {
        findpath(root->right,ls,ls_idx+1,res); 
    }
    return;
 
}

score 0 · Answer 1 · answered Mar 09 '22 at 15:42

The last argument to your findPath function is declared as a char** type; thus, when you make the call findpath(root,&ls[0],0,res); in binaryTreePaths, where the res variable is a char** type, a copy of that pointer is passed to the findPath function (most likely, but not necessarily, by placing that copy on the stack).

Then, if reallocation is required, the res = (char **)realloc(res,sizeof(char *) * sum); line in that function overwrites the value in the passed copy and, at the same time (if the call is successful – vide infra), will (probably) invalidate (i.e. free) the memory referenced by the previous address in that res copy. Thus, when control returns to the calling binaryTreePaths function, its own version of res will not have been modified and will remain pointing to that (now invalid) memory.

So, in order for your findPath function to be able to modify the given res argument, that must be passed as a pointer – in this case, a pointer to a char**, which will be of type char***; then, when called, you will need to pass the address of the res variable in binaryTreePaths.

Note also that directly overwriting a pointer in a call to realloc, as you have done in the line of code quoted above is dangerous. This is because, should that call fail, then you have lost the original data pointer (it will have been overwritten with NULL) and error recovery will be very difficult. You should save the return value in a temporary variable and only replace your original if the call succeeds.

With the code you have provided, I cannot properly test for any other errors but, taking the points above in hand, the below is a possible fix. See also: Do I cast the result of malloc?

int sum;
int resIdx;
void findpath(struct TreeNode* root, int* ls, int ls_idx, char*** res); // Note last argument type!

char** binaryTreePaths(struct TreeNode* root, int* returnSize)
{
    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }
    resIdx = 0;
    sum = 10;
    char** res = malloc(sizeof(char*) * sum);
    int ls[100];
    findpath(root, &ls[0], 0, &res); // Pass ADDRESS of res
    *returnSize = resIdx;
    return &res[0];
}

void findpath(struct TreeNode* root, int* ls, int ls_idx, char*** res)
{
    char temp[100];
    int l = 0, i = 0;
    if (root->left == NULL && root->right == NULL) {
        ls[ls_idx] = root->val;
        ls_idx += 1;
        if (resIdx >= sum) {
            sum = sum + 10;
            char** test = realloc(*res, sizeof(char*) * sum);
            if (test == NULL) {
                // Handle/signal error
                return;
            }
            *res = test; // Only replace original if realloc succeeded!
        }
        (*res)[resIdx] = malloc(sizeof(char) * 100);
        while (i < ls_idx) {
            if (i == 0) {
                l = l + sprintf(&temp[l], "%d", ls[i]);
            }
            else {
                l = l + sprintf(&temp[l], "->%d", ls[i]);
            }
            i++;
        }
        strcpy((*res)[resIdx], temp);
        resIdx++;
        return;
    }
    ls[ls_idx] = root->val;
    if (root->left != NULL) {
        findpath(root->left, ls, ls_idx + 1, res);
    }
    if (root->right != NULL) {
        findpath(root->right, ls, ls_idx + 1, res);
    }
    return;
}

What's wrong with my realloc doing on 2d-array

1 Answers1