C issue: int value in struct is weird when using assignment via pointers-CodePudding

I'm quite new in C and wanted to write code for a Binary-Tree with methods for inserting, deleting and wahtever. In the code, I use value = 0 in order to show that the struct is undefined yet. (I don't know any better way). Problem: We shouldn't insert the value 0. The main problem I have: Why does printf("%d\n", root.pLeft->value); print the number 6422476 instead of 3?? Here is the whole code: `

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

struct Node {
    int value;
    struct Node *pLeft;
    struct Node *pRight;
};

void insert(struct Node *root, int value) {
    struct Node *current = root;
    while (current->value != 0) {
        if (value < current->value) {
            current = current->pLeft;
        } else {
            current = current->pRight;
        }
    }
    current->value = value;
    struct Node newLeft;
    newLeft.value = 0;
    struct Node newRight;
    newRight.value = 0;
    current->pLeft = &newLeft;
    current->pRight = &newRight;
}

int main() {
    struct Node root;
    root.value = 0;

    insert(&root, 4);
    insert(&root, 3);

    printf("%d\n", root.value);
    printf("%d\n", root.pLeft->value);
    
    return 0;
}

CodePudding user response：

Problem is here:

    struct Node newLeft;
    newLeft.value = 0;
    struct Node newRight;
    newRight.value = 0;
    current->pLeft = &newLeft;
    current->pRight = &newRight;
}

newLeft and newRight are local varialbes in storage class "auto", thus they will die (end their lifetime) at the end of the enclosing block.

But you are using (the addresses to) these objects outside the block because their address escape the block. So you have dangling pointers.

Solution is to dynamically allocate the objects by meand of malloc and free.

CodePudding user response：

Within the function insert data members pLeft and pRight are set to addresses of local objects with automatic storage duration.

current->value = value;
struct Node newLeft;
newLeft.value = 0;
struct Node newRight;
newRight.value = 0;
current->pLeft = &newLeft;
current->pRight = &newRight;

These objects newLeft and newRight will not be alive after exiting the function. So the pointers pLeft and pRight will be invalid and dereferencing them will invoke undefined behavior.

Your approach is wrong. You need to use pointers of the type struct Node that will point to dynamically allocated nodes in the tree. Start from this declaration in main

struct Node *root = NULL;

and then the function insert will dynamically allocate nodes of the tree if it is required.

The function can be defined for example the following wat

struct Node { int value; struct Node *pLeft; struct Node *pRight; };

int insert( struct Node **root, int value ) 
{
    while ( *root != NULL ) 
    {
        if ( value < ( *root )->value ) 
        {
            root = &( *root )->pLeft;
        } 
        else 
        {
            root = &( *root )->pRight;
        }
    }

    struct Node *new_node = malloc( sizeof( *new_node ) );
    int success = new_node != NULL;

    if ( success )
    {
        new_node->value  = value;
        new_node->pLeft  = NULL;
        new_node->pRight = NULL;

        *root = new_node;
    }

    return success;
}

And the function is called like

struct Node *root = NULL;

insert( &root, 4 );
insert( &root, 3 );

printf( "%d\n", root->value );
printf( "%d\n", root->pLeft->value );