Home > Blockchain >  SIGSEGV on access to pointer to left node of binary tree, even though the pointer is initialized
SIGSEGV on access to pointer to left node of binary tree, even though the pointer is initialized

Time:06-08

I am trying to create a function which returns the mirrored copy of a binary tree. By "mirrored" I mean a tree with each left node as its right node and vice versa.

Visual example from the page I'm taking this exercise from.

The one on the left gets copied to resemble the one on the right. This is the code of the function, with the definition of the binary nodes and "insert node" function that I use:

typedef struct bNode {
    int data;
    struct bNode *left;
    struct bNode *right;
} bNode;
    
//  =============================================================
    
bNode* reverse_tree (bNode **tree) {
    bNode *copy = malloc(sizeof(bNode));
    copy->data = (*tree)->data;
    if (!((*tree)->right) && !((*tree)->left)){
        return copy;
    }
        
    copy->left = reverse_tree(&(*tree)->right);
    copy->right = reverse_tree(&(*tree)->left);
    return copy;
}
    
//  =============================================================
    
void insert(bNode **tree, int data) {
    bNode *temp, *previous, *current;

    if (*tree == NULL) {
        temp = (bNode *) malloc(sizeof (bNode));
        temp->data = data;
        temp->left = NULL;
        temp->right = NULL;
        *tree = temp;
        return;
    }

    if (data < (*tree)->data) {
        insert(&(*tree)->left, data);
    } else if (data > (*tree)->data) {
        insert(&(*tree)->right, data);
    }
}

After some troubleshooting, one single layer of recursion works fine, but after that, the pointers break (that is, they point to an inaccessible part of memory), and the program receives a SIGSEGV Segmentation fault.

Why do I receive this SIGSEGV and how do I avoid it?

P.S I am quite inexperienced with pointers; I hope it's not too bad.

(The one on the left gets copied to resemble the one on the right)

CodePudding user response:

At least the function reverse_tree has a bug.

The sub-statement of this if statement

if (!((*tree)->right) && !((*tree)->left)){
    return copy;
}

gets the control when the both pointers, right and left, are null pointers.

So this code snippet

copy->left = reverse_tree(&(*tree)->right);
copy->right = reverse_tree(&(*tree)->left);

can get the control when only one of the pointers is a null pointer.

In this case in teh next recursive call of the function this statement

copy->data = (*tree)->data;

invokes undefined behavior for the passed null pointer.

  • Related