CODEWITHSUNDEEP
cdata-structures
Jeremy Robertson
Jeremy Robertson

Reputation: 115

Difficulties implementing a binary search tree in C

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);
}

Upvotes: 0

Views: 118

Answers (3)

vonbrand
vonbrand

Reputation: 11831

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.

Upvotes: 1

tkdkop
tkdkop

Reputation: 129

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.

Upvotes: 1

Deduplicator
Deduplicator

Reputation: 45704

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)

Upvotes: 1

Related Questions