AllAnimals AllAnimals - 1 month ago 5
C Question

Binary tree implementation gives me segmentation fault in C

I'm getting a segmentation fault when trying to access data stored in my TreeNode. Here is the code:

#include <stdio.h>
#include <stdlib.h>

typedef struct NodeTag{
int value;
struct NodeTag *LLink;
struct NodeTag *RLink;
} TreeNode;

void inOrder(TreeNode * n){
if(n->LLink != NULL)
inOrder(n->LLink);
printf("%d ", n->value);
if(n->RLink != NULL)
inOrder(n->RLink);
}

void newNode(TreeNode * n, int v){
n = malloc(sizeof(TreeNode));
n->value = v;
n->LLink = NULL;
n->RLink = NULL;
}

void addValue(TreeNode * r, int value){

if(value < r->value){
if(r->LLink == NULL){
newNode(r->LLink, value);
} else {
addValue(r->LLink, value);
}
} else if (value > r->value) {
if(r->RLink == NULL){
newNode(r->RLink, value);
} else {
addValue(r->RLink, value);
}
}
}



int main(){

TreeNode * root = 0;
newNode(root, 1);
printf("%d\n", root->value); //<--This is where I get the fault
//addValue(root, 3);
//addValue(root, 10);
//addValue(root, 2);

//inOrder(root);

return 0;
}


If anyone can explain to me why I'm getting this error it would be greatly appreciated. I'm a student learning C and I'm not too familiar with pointers and such.

Answer
void newNode(TreeNode * n, int v){
    n = malloc(sizeof(TreeNode));
    n->value = v;
    n->LLink = NULL;
    n->RLink = NULL;
}

In this code, n is a pointer to a TreeNode struct but if you assign something to n, this is not visible outside of the function as the pointer is passed by value.

void writeToA ( int a ) {
    a = 5;
}

int main ( ) {
    int x = 10;
    writeToA(x)
    printf("%d\n", x);
}

What will this code print? It will print 10, not 5. That's because the value of x is passed to the function, not a reference to x. Changing that value within the function will not change the value of x outside the function.

A pointer is also a value, basically it is an int and the int value is a memory address:

void writeToPtr1 ( int * a ) {
    int i = 10;
    a = &i; // `a` now points to the memory address of i
}

void writeToPtr2 ( int * a ) {
    *a = 5; // This doesn't change where `a` points to,
    // it writes 5 to the memory address to that `a` points to.   
}

int main ( ) {
    int x = 10;
    int *ptr = &x; // ptr now points to the memory address of x!
    writeToPtr1(ptr);
    // ptr still points to the memory address of x!
    // As not a reference to ptr was passed, the memory
    // address of x was passed to the function!

    writeToPtr2(ptr);
    // ptr still points to the memory address of x!
    // But this memory now has the value 5 and not 10 anymore.
}

You need to return the result of the allocation:

TreeNode * newNode ( int v ) {
    TreeNode * n = malloc(sizeof(TreeNode));
    n->value = v;
    n->LLink = NULL;
    n->RLink = NULL;
    return n;
}

int main ( ) {
    TreeNode * root = newNode(1);
    printf("%d\n", root->value);
    return 0;
}

Or you need to pass a reference to the pointer and then change the value the pointer points to:

 void newNode ( TreeNode ** outNode, int v ) {
    // TreeNode ** is a pointer to a pointer to a TreeNode!
    TreeNode * n = malloc(sizeof(TreeNode));
    n->value = v;
    n->LLink = NULL;
    n->RLink = NULL;
    *outNode = n; // Make the pointer point to `n`
}

int main ( ) {
    TreeNode * root = NULL;
    newNode(&root, 1); // Pass a pointer to root
    printf("%d\n", root->value);
    return 0;
}