Why try to print the value in the left node and right node of the binary search tree causing a Segme-CodePudding

I am trying to implement the insert operation of a binary search tree using C. Why does the following code show a Segmentation fault when trying to print the value of the left and right nodes of the root? Please explain what caused this error exactly.

#include <stdio.h>
#include <stdlib.h>
struct node {
    int data;
    struct node* left;
    struct node* right;
};

struct node *root, *temp = NULL;

void insert(int data) {
    struct node *newNode = (struct node*) malloc(sizeof(struct node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    
    if (root == NULL){
        // if tree is empty insert the node as root
        root = newNode;
    }else {
        // if the tree is not empty
        temp = root;
        while(temp != NULL) {
            if(data <= root->data) {
                temp = temp->left;
            }
            if(data > root->data) {
                temp = temp->right;
            }
        }
        temp  = newNode;
    }
}
int main() {
    insert(7);
    insert(4);
    insert(8);
    printf("\n\n------%d------", root->left->data);
    printf("\n\n------%d------", root->right->data);
    return 0;
}

CodePudding user response：

The assignment temp = newNode only stores a pointer in the temp variable, not somewhere in the tree. So your tree's root node will never get any child. By consequence the main program is dereferencing a root->left pointer that is NULL, and this explains the error you get.

In order to really attach the new node at the right place in the tree, you need to modify a left or right member of some node. You can do this in several ways. One is to make temp a pointer-pointer, so that it will have the address of a left or right member. Then the assignment to *temp, will be an assignment to a node's left or right member, effectively extending the tree with that new node.

Here is the updated part of the code:

        struct node **temp = &root;
        while(*temp != NULL) {
            if(data <= root->data) {
                temp = &(*temp)->left;
            }
            if(data > root->data) {
                temp = &(*temp)->right;
            }
        }
        *temp = newNode;

CodePudding user response：

first, you run temp to respective place in tree for data; however, then you reset temp back to NewNode - that is, temp now points back to standalone NewNode. you do this several times with insert(), but the data is lost immediately, as I explained.

you are effectively trying therefore to print data that no longer exists.

a simple fix would be:

void insert(int data) {
struct node *newNode = (struct node*) malloc(sizeof(struct node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;

if (root == NULL){
    // if tree is empty insert the node as root
    root = newNode;
}else {
    // if the tree is not empty
    temp = root;
    while(temp != NULL) {
        if(data <= root->data) {
            temp = temp->left;
        }
        if(data > root->data) {
            temp = temp->right;
        }
    }
    temp->data=data;
}}

hope that helps!