CODEWITHSUNDEEP
cruntime-error
mvw12
mvw12

Reputation: 3

Run time error on C that I am unable to detect

My program inputs a sequence of elements and checks if a up to down sequence of the same numbers exists in a binary tree.

To be clear, I am submitting my answer to a system set up by my professor that just responds with a Failed - run time error, with no other details. When I compile and run it on Xcode, it works perfectly fine with no run time errors. I have checked for divide by zero, memory leakage, array out of bounds etc but I can't seem to spot the error. For this reason my code will be a bit lengthy because I can't figure out the problematic part.

node *n;

node *newNode(int data)
{
    node *new_node = (node *)malloc(sizeof(node));
    new_node->number = data;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;
}

node *insert(int arr2[], node *ptr, int i, int M2, int x)
{
    if (i < M2)
    {
        node *temp = newNode(arr2[i]);
        ptr = temp;
        if (ptr -> number == x)
            n = ptr; // n is a global variable of type node*
        ptr->left = insert(arr2, ptr->left, 2 * i + 1, M2, x);
        ptr->right = insert(arr2, ptr->right, 2 * i + 2, M2, x);
    }
    return ptr;
}

void checkPath(int arr1[], node *ptr, int *i, int M1)
{
    node *temp = (node *)malloc(sizeof(node));
    if (n == NULL)
        return;
    while ((*i) < M1)
    {
        if (n->left->number == arr1[*i])
        {
            (*i)++;
            temp = n->left;
            n = temp;
        }
        else if(n->right->number == arr1[*i])
        {
            (*i)++;
            temp = n -> right;
            n = temp;
        }
        else
            break;
    }
}

int main()
{
    int N, M1, M2, z;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        z = 1;
        scanf("%d", &M1);
        int arr1[M1];
        for (int j = 0; j < M1; j++)
            scanf("%d", &arr1[j]);
        scanf("%d", &M2);
        int arr2[M2];
        for (int k = 0; k < M2; k++)
            scanf("%d", &arr2[k]);
        node *ptr = (node *)malloc(sizeof(node));
        ptr = insert(arr2, ptr, 0, M2, arr1[0]);
        checkPath(arr1, ptr, &z, M1);
        if (z == M1)
            printf("True\n");
        else
            printf("False\n");
        free(ptr);
    }
    return 0;
}

Sorry for the lengthy piece of code. Thanks in advance!

Upvotes: 0

Views: 77

Answers (3)

Bokrenok
Bokrenok

Reputation: 21

Consider adding pointer checks before accessing 'left' or 'right'

    if (n->left && n->left->number == arr1[*i])

and

    else if(n->right && n->right->number == arr1[*i])

Upvotes: 0

Bokrenok
Bokrenok

Reputation: 21

What about input data? Is it guaranteed to be OK or not?

There is no validation at data input in the code.

Well, I've just reproduced the failure:

./test 
2
1
1
1
1
True
2
2
2
2
2
2
    Segmentation fault (core dumped)

Given that 'node' is this:

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

But the actual error in logic I didn't find yet. BTW the logic is somewhat curious.

P.S. this input would also give a crash:

./test 
2
2
2
2
2
2
2
2

Segmentation fault (core dumped)

Upvotes: 0

chux
chux

Reputation: 153517

At least this problem: lost memory.

checkPath() never uses the result of malloc(). This suggest a logical error in this function.

void checkPath(int arr1[], node *ptr, int *i, int M1)
{
    node *temp = (node*) malloc(sizeof(node));
    ...
    while((*i) < M1)
      ... 
            temp = n -> left;
            n = temp;
      ...
            temp = n -> right;
            n = temp;
      ...
    }
}

It is concerning code is reading and setting a global variable n here.

This may or may not be a key problem.

Upvotes: 1

Related Questions