C Binary Search Tree Insertion Pointer Issue

Question

I am trying to implement binary search tree insertion but running into problems.

I have implemented the tree using the following Node and Tree structs

typedef struct Node {
    double value;

    struct Node *parent;
    struct Node *right_child;
    struct Node *left_child;
} Node;

typedef struct Tree {
    struct Node *root;
} Tree;

The following is the insert function

void insert(Tree *t, Node n) {

    Node *x = t->root, *y = NULL;

    //follow tree down until we reach a leaf of the tree
    while (x != NULL) {

        //save last non-NULL value. We will insert node n as a child to this leaf.
        y = x;

        if (n.value < x->value) {
            x = x->left_child;
        } else {
            x = x->right_child;
        }

    }

    //The parent of the node to insert is the leaf we reached
    n.parent = y;

    //If n is greater than y then it is its right child and vice-versa.
    if (n.value > y->value) {
        y->right_child = &n;
    } else {
        y->left_child = &n;
    }

}

When I run this in my main method

int main(void) {

    Node n1;
    Node n2;
    Node n3;


    n1.value = 4;
    n1.parent = NULL;
    n1.left_child = NULL;
    n1.right_child = NULL;

    n2.value = 2;
    n2.parent = NULL;
    n2.left_child = NULL;
    n2.right_child = NULL;

    n3.value = 1;
    n3.parent = NULL;
    n3.left_child = NULL;
    n3.right_child = NULL;

    Tree t;

    t.root = &n1;

    insert(&t,n2);

    insert(&t,n3);

    printf("n1 left child %f \n", n1.left_child->value);

    return EXIT_SUCCESS;
}

It prints n1 left child 1.000000 which is incorrect. It should be 2. I have tried inserting print statements for debugging and it appears that the insert function is assigning children at the end to the wrong pointer (i.e. the n2 node is not persisting after it is inserted). So I think this means there is something wrong with y. I don't think y is representing what I want it to which is a pointer to the leaf node in the tree (where I will insert the new node n).

Iharob Al Asimi · Accepted Answer · 2015-09-20 01:17:08Z

1

You are taking the address of a temporary variable, and you dereference it after it's deallocated and that means your program invokes undefined behavior. In

void insert(Tree *t, Node n)

The Node n parameter is allocated within the stack frame of the insert() function, when the function returns the frame is destroyed leading to n being deallocated.

You hold a pointer to it's address in Tree *t;, accessing that pointer is invalid after the function has returned.

You must pass a pointer to the address of n2 and n3 from main(), like this

insert(&t, &n2);
insert(&t, &n3);

and change insert() to directly accept the pointer instead of a local copy of the instance.

With my suggested solution n2 and n3 are allocated within the stack frame of main() and thus have a lifetime equal to the whole program lifetime, since you would be passing their address the pointers to the nodes in your tree would still point to valid memory after insert() has returned and you will be able to print their contents without invoking undefined behavior.

edited Sep 20, 2015 at 1:17

answered Sep 20, 2015 at 1:04

Iharob Al Asimi

53.1k6 gold badges66 silver badges100 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user1893354 Over a year ago

Thanks. This makes sense. Inside the insert function I am setting the child pointer to a memory address that is being destroyed after the function finishes. But I still don't quite understand why the last print statement would be n1 left child 1.000000. I suppose this would be the undefined behaviour you are referring to? I would think the n3 temporary variable would have been destroyed by that point.

Iharob Al Asimi Over a year ago

Yes it depends on many things, except on the actual code. It's not predictable, at least no easily predictable. Many possible effects are possible when undefined behavior happens, including a crash.

Collectives™ on Stack Overflow

C Binary Search Tree Insertion Pointer Issue

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related