Binary Search Tree not adding Element

Question

I have a binary search tree for which I'm trying to implement an insert function. However when I test the code, I see that no element is getting added at all even though my logic seems fine to me. I feel like there is some C idiosyncrasy that I'm missing.

struct tree_element {
    int data;
    struct tree_element* left;
    struct tree_element* right;
};

typedef struct tree_element node;

void init(node* root){
    root->left = NULL;
    root->right = NULL;
    root->data = 0;
}

void insert(node* root, int val){
    if (root == NULL){
        root = (node*)(malloc(sizeof(node)));
        init(root);
        root->data = val;
        printf("added %i\n", val);
        return;
    }

    if (val > root->data){
        insert(root->right, val);
    }
    else {
        insert(root->left, val);
    }
}

You need to use a double-pointer (a pointer to a pointer), but it's actually easier to return the node as the function result in insert. — 500 - Internal Server Error
– 500 - Internal Server Error, Commented Jun 26, 2016 at 22:55
Why would a double pointer be necessary? And what about the current code is preventing nodes from being added? — Quinn McHugh
– Quinn McHugh, Commented Jun 26, 2016 at 22:56
When you do insert(root->right, ... you are passing a copy of the right pointer - the value that you (might) assign in insert never makes it back out. — 500 - Internal Server Error
– 500 - Internal Server Error, Commented Jun 26, 2016 at 22:58

Andrew Shepherd · Accepted Answer · 2016-06-26 22:59:14Z

1

You change the root value within the function. However, from the calling function perspective, nothing is changed.

This might work:

void insert(node** root, int val){
    if (*root == NULL){
        *root = (node*)(malloc(sizeof(node)));
        init(*root);
        (*root)->data = val;
        printf("added %i\n", val);
        return;
    }
    if (val > (*root)->data){
        insert(&((*root)->right), val);
    }
    else {
        insert(&((*root)->left), val);
    }
}

The fundamental concept is - when you pass in a pointer to a method, the method can change the data that the pointer is pointing to, but cannot alter the pointer itself.

answered Jun 26, 2016 at 22:59

Andrew Shepherd

45.5k33 gold badges148 silver badges212 bronze badges

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

2 Comments

P. Kouvarakis Over a year ago

While functionally identical, it might be easier/clearer to use a pointer reference instead of double pointer (i.e. node* &root instead of node**).

nbro Over a year ago

@P.Kouvarakis Not in C, at least, my friend.

Collectives™ on Stack Overflow

Binary Search Tree not adding Element

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related