Binary tree - not able to add values

Question

In the below program, I am trying to populate a BST with the values present in an array arr. The program seems to run in a loop for a long time and then I get a segmentation fault. Can somebody please explain what I am missing here?

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

void add(struct node **root, int i);
int arr[14] = {30, 50, 25, 32, 45, 55, 20, 27, 31, 43, 47, 52, 88};

int main(void)
{
        struct node *root = malloc(sizeof(struct node));
        root->value = 35;
        root->left = NULL;
        root->right = NULL;

        struct node *start = root;
        int i;

        for (i = 0; i < 13; i++) {
                add(&root, arr[i]);
                root = start;
        }

        printf("%d\n", root->value);
        printf("%p\n", root->right);
        printf("%p\n", root->left);
}

void add(struct node **root, int i)
{
        while ((*root) != NULL) {
                printf("left: %p\n", (*root)->left);
                if (i < (*root)->value) {
                        add(&((*root)->left), i);
                } else {
                        add(&((*root)->right), i);
                }
        }
        *root = malloc(sizeof(struct node));
        (*root)->value = i;
        (*root)->left = NULL;
        (*root)->right = NULL;
}

Show source
| C   | data-structures   | algorithm   | binary-search-tree   2017-01-07 19:01 1 Answers

Answers ( 1 )

  1. 2017-01-07 20:01

    You're using recursion, so there is no reason for the while to even be there. It should be an if-else logical construct:

    void add(struct node **root, int i)
    {
        if (*root)
        {
            if (i < (*root)->value) {
                add(&((*root)->left), i);
            } else {
                add(&((*root)->right), i);
            }
        }
        else
        {
            *root = malloc(sizeof(struct node));
            (*root)->value = i;
            (*root)->left = NULL;
            (*root)->right = NULL;
        }
    }
    

    If the goal was to eliminate the recursion, then the solution is to use the while-loop, but move root down the tree until it addresses an empty node:

    void add(struct node **root, int i)
    {
        while(*root)
        {
            if (i < (*root)->value) {
                root = &(*root)->left;
            } else {
                root = &(*root)->right;
            }
        }
        *root = malloc(sizeof(struct node));
        (*root)->value = i;
        (*root)->left = NULL;
        (*root)->right = NULL;
    }
    

    Finally, the for-loop in main unnecessarily resets root repeatedly. Properly done that loop should just look like this (assuming the goal is to host only the values in the array):

    int main(void)
    {
        struct node *root = NULL;
    
        int i;
        for (i = 0; i < 13; i++)
            add(&root, arr[i]);
    
        printf("%d\n", root->value);
        printf("%p\n", root->right);
        printf("%p\n", root->left);
    }
    
◀ Go back