Difficulties implementing a binary search tree in C

Question

I've been trying to implement a binary search tree in C for a few hours now, and I narrowed down my main problem to the insertion function, which you see below. What appears to be the problem is that when I set root to null, and then try to insert, it creates the root node over and over but nothing changes (I get the "forming root node message" several times, traversal doesn't work). However, when I uncomment the line //root = newNode(3,NULL,NULL);, and manually create the root node, all my insertions work fine and my inorder traversal works. I'd like to be able to create the root node in my function, and not manually like this. This has been frustrating me for a while, so any help at all would be appreciated. Thanks!

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

struct node {
    int key;
    struct node* left;
    struct node* right;
};

struct node* newNode(int val, struct node* lchild, struct node* rchild) {
    struct node* temp = malloc(sizeof(struct node));
    if(temp == NULL) { printf("Error creating node! Exiting."); exit(1); }

    temp->key = val; 
    temp->left = lchild; 
    temp->right = rchild;
    return(temp);
}           

void add(int val, struct node* current) {
    if (current == NULL) {
        printf("forming root node\n");
        current = newNode(val,NULL,NULL);   
    } else if (val <= current->key) {
        if (current->left == NULL) {
            current->left = newNode(val, NULL, NULL);
        } else {
            add(val, current->left);            
        }
    } else {
        if (current->right == NULL) {
            current->right = newNode(val, NULL, NULL);
        } else {
            add(val, current->right);
        }
    }
}

void inOrder(struct node* current) {
    if (current != NULL) {
        inOrder(current->left);
        printf("%d ", current->key);
        inOrder(current->right);
    }
}

int main() {
    struct node* root = NULL;

    //root = newNode(3,NULL,NULL);
    add(3, root);
    add(2, root);
    add(4, root);
    add(16, root);
    inOrder(root);
}

Deduplicator · Accepted Answer · 2014-04-05 21:25:48Z

1

C is pass-by-value only. If you want to return data from a function, you must either pass a pointer to the data which shall be modified or return it. Your add()-function currently does neither.

My advise is, use a return value.
Possible corrected prototypes:

struct node* add(int val, struct node* current)
void add(int val, struct node** current)

answered Apr 5, 2014 at 21:25

Deduplicator

46k7 gold badges73 silver badges125 bronze badges

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

Comments

tkdkop · Accepted Answer · 2014-04-05 21:33:51Z

1

It is because you are passing in the value of the root node by value. In main() you create a node* (root) and set it to NULL. This means that root contains a memory address of 0. The problem is that no value is returned, therefore no matter what you do in add(), the value of root remains NULL, or 0. When you manually create a root node, it works because add() can modify the memory at the address it is given, and the value of root points somewhere meaningful so these changes persist, but when root is null, all of the changes made by add() are lost.

answered Apr 5, 2014 at 21:33

tkdkop

1291 silver badge6 bronze badges

Comments

vonbrand · Accepted Answer · 2014-04-05 23:19:37Z

1

You want to modify the current pointer, pass a pointer to it.

void add(int val, struct node **ptree);
{
    if(*ptree == NULL) {
        struct node *tmp = malloc(sizeof(*tmp));
        tmp->val = val; tmp->left = tmp->right = NULL;

        *ptree = tmp;
    }
    else if (val == (*ptree)->val)
        /* Scream about duplicate insertion */
    else if (val < (*ptree)->val)
        add(val, &((*ptree)->left));
    else /* val > (*ptree)->val */
        add(val, &((*ptree)->right));
 }

to be called as e.g. add(42, &tree); if tree is (to be) the pointer to the root.

edited Apr 5, 2014 at 23:19

answered Apr 5, 2014 at 21:34

vonbrand

11.9k8 gold badges36 silver badges54 bronze badges

Collectives™ on Stack Overflow

Difficulties implementing a binary search tree in C

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related