Runtime error on realloc() | inorder traversal

Question

I am trying to implement an inorder traversal that returns an array with the traversed values. In my recursive approach, I am trying to use realloc() function to modify the size of the array and store the result. However, I am getting the following error:

realloc(): invalid next size.

Following is my code:

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void inorder(struct TreeNode *root, int *res, int *returnSize)
{
    if(root == NULL)
        return;

    //if left node present, traverse left
    inorder(root->left,res,returnSize);

    // add node to array
    res[(*returnSize)]=root->val;
    (*returnSize)++;
    int *temp = realloc(res,sizeof(int)*(*returnSize)); 
    res = temp;

    //if right node present, traverse right
    inorder(root->right,res,returnSize);
}

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* inorderTraversal(struct TreeNode* root, int* returnSize) 
{
    //check if root == null
    if(root == NULL)
    {
        return root;
    }

    //malloc result array to return
    int *res = (int *)malloc(sizeof(int)*(*returnSize));

    //start inorder parsing
    inorder(root, res, returnSize);

    return res;
}

For one thing you fail to check the return value of `realloc()`. And what is `*returnSize` before calling this? — John Zwinck, Oct 21 '17 at 02:36
See: [**Do I cast the result of malloc?**](http://stackoverflow.com/q/605845/995714). Also `int *temp = realloc (res, sizeof *temp * return Size); if (!temp) return res; res = temp;` will validate the return of `realloc` and prevent loss of the pointer to `res` in the event `realloc` fails. — David C. Rankin, Oct 21 '17 at 03:00
Note that `res` in `inorderTraversal` isn't updated in `inorder` because call-by-value. — BLUEPIXY, Oct 21 '17 at 08:15

chqrlie · Accepted Answer · 2017-10-21T12:23:00.493

There are multiple problems:

the reallocated value for res is not passed back to the caller. You should pass a pointer to res instead of its value or return the newly allocated pointer.
returnSize is an output variable, you should initialize it to 1, or better to 0 and reallocate the array before storing the node value.
you should handle potential memory allocation failures.

Here is a corrected version:

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

int *inorder(struct TreeNode *root, int *res, int *returnSize) {
    if (root != NULL) {
        //traverse the left tree
        res = inorder(root->left, res, returnSize);

        if (returnSize >= 0) {
            // add node to array
            int *temp = realloc(res, sizeof(int) * (*returnSize) + 1); 
            if (temp == NULL) {
                free(res);
                *returnSize = -1;
                res = NULL;
            } else {
                res = temp;
                res[(*returnSize)++] = root->val;

                //traverse the right tree
                res = inorder(root->right, res, returnSize);
            }
        }
    }
    return res;
}

/**
 * Return an array of size *returnSize.
 * Return NULL and *returnSize=0 for an empty tree.
 * Return NULL and *returnSize<0 for memory allocation failure.
 * Note: The returned array is malloced, the caller must call free().
 */
int *inorderTraversal(struct TreeNode *root, int *returnSize) {
    int *res = NULL;

    *returnSize = 0;
    return inorder(root, res, returnSize);
}

score 0 · Answer 2 · answered Oct 21 '17 at 02:37

0

You almost certainly have memory corruption elsewhere in your code--this code looks good to me (well, apart from not testing the return from realloc() for NULL, but that would just cause you to lose data, not get the error you are seeing). If you can run valgrind on your program it will probably point you to the problem.

answered Oct 21 '17 at 02:37

One Guy Hacking

1,176
11
16

So this is my solution for a leetcode problem ( https://leetcode.com/problems/binary-tree-inorder-traversal/description/ ). It works for some cases but throws this error for other cases. – chandana Oct 21 '17 at 03:01
It really sounds like memory corruption to me. I think valgrind would probably go a long way towards pointing you to your bug. – One Guy Hacking Oct 21 '17 at 03:04

Runtime error on realloc() | inorder traversal

2 Answers2