BST program in C

Question

Please help me with this. I keep getting seg faults! I want to use recursion to create and insert a new node. Please help me debug this.

//Create a Binary Search Tree From an array.
struct Tree
{
        int data;
    struct Tree *lchild;
    struct Tree *rchild;
};
struct Tree *root = NULL;
struct Tree *node(int val)
{
    struct Tree *tempnode;
    tempnode = (struct Tree*)malloc(sizeof(struct Tree));
    tempnode->data = val;
    tempnode->rchild = NULL;
    tempnode->lchild = NULL;
    return tempnode;
}

void createTree(struct Tree *curr, int val)
{
    struct Tree *newnode = node(val);

    if (curr == NULL)
        curr = newnode;
    else if(val < curr->data)
    {
        createTree(curr->lchild,val);
    }
    else if(val > curr->data)
    {
        createTree(curr->rchild,val);

    }
    else
        printf("Error Similar data found\n");
}

void inorder(struct Tree *root)
{
    if (root->lchild != NULL)
        inorder(root->lchild);
    printf("[%d]    ",root->data);
    if (root->rchild != NULL)
        inorder(root->rchild);
}
int main()
{
//    root = NULL;
    int i = 0, arr[5] = {41,12,32,23,17};
    for(i;i<5;i++)
        createTree(root,arr[i]);
    inorder(root);
    return 0;
}

why do I keep getting seg fault. Can someone explain me? Am I doing something I should not? Or am I missing at some point?

[Please don't cast the return value of `malloc()` in C](http://stackoverflow.com/a/605858/28169). — unwind, Nov 19 '13 at 18:20

Arkku · Answer 1 · 2013-11-19T18:23:20.787

The root of the tree is not assigned anywhere; in your function createTree you probably think that it is assigned in:

if (curr == NULL)
    curr = newnode;

But curr is local to the function and does not affect root. You need to change the argument curr to be a pointer to pointer, otherwise the function does not work for assigning the root node, or child nodes. The root of the tree is not assigned anywhere; in your function createTree you probably think that it is assigned in:

if (curr == NULL)
    curr = newnode;

But curr is local to the function and does not affect root even if you gave it as the argument curr. You need to change the argument curr to be a pointer to pointer, otherwise the function does not work for assigning the root node, or child nodes. That is, the function declaration becomes:

void createTree(struct Tree **curr, int val)

Of course you must then change the use of curr inside the function accordingly (i.e., the address pointed to is *curr where it used to be curr), calls of the function need to pass the address, and not value, of the pointer (e.g., createTree(&root, arr[i])).

edit: Or, indeed, have the function return curr and always assign the return value to the relevant pointer at every place where you call createTree, thanks to @JonathanLeffler for the observation.

Alternatively, use `struct Tree *createTree(struct Tree *curr, int val)` and `return curr;` at the end and invoke it as `root = createTree(root, arr[i]);`. — Jonathan Leffler, Nov 19 '13 at 18:21
@JonathanLeffler Yes, good point, that would indeed be simpler for this function, I edited the answer accordingly. — Arkku, Nov 19 '13 at 18:27

score 2 · Answer 2 · answered Nov 19 '13 at 18:19

Learn to use a debugger!

Stepping through the main function, you would have seen that the value of root would have remained NULL after each call to createTree

The createTree function is not modifying the value of root, but only modifying its copy of the value of root.

Your createTree function needs to take a struct Tree **curr, a pointer-to-a-pointer. This allows the function to modify the original value, not the local copy.

BST program in C

2 Answers2