CODEWITHSUNDEEP
calgorithmbinary-search-tree
user1893354
user1893354

Reputation: 5938

C Binary Search Tree Insertion Pointer Issue

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

Upvotes: 0

Views: 155

Answers (1)

Iharob Al Asimi
Iharob Al Asimi

Reputation: 53006

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.

Upvotes: 1

Related Questions