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.
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.