Binary Tree in C - Troubles

Question

typedef struct node
{
    struct node *leftChild, *rightChild;
    int value;
} bst;

void insert(bst* b, int i)
{
                b=malloc(sizeof(b));
                b->value=i;
                b->leftChild = NULL;
                b->rightChild = NULL;
                printf("[%i]",b->value);
                return;
}
main()
{
  bst* b;
  insert(b,5);
  printf("[%i]",b->value);
}

The second printf causes a Segmentation Fault, commenting it out it works fine. What am I doing wrong here (Ignore the meanings of the function names i.e. that the insert is an insert function for the bst)? Shouldn't bst persist in it's setup outside of the insert function?

Answer 1

bst* b; declares a pointer... but doesn't allocate the actual structure. allocate and initialize b and you'll be onto your next step.

This is slightly a style discussion but your main should look either like this.

main()
{
  bst *b;
  b = (bst*)malloc(sizeof(bst));
  /* more initialization */
  insert(b, 5);

  free(b);
}

or like this

main()
{
  bst *b;
  bst_new(&b);
  insert(b, 5);
  bst_free(&b);
}

Answer 2

You need to pass the pointer by reference to change where it points.

// just add this & here in the function definition.
// That's the only change in all your code (for c++)
void insert(bst * &b, int i)

Or in C, a pointer pointer

void insert(bst ** b, int i)
{
                *b=malloc(sizeof(*b));
                (*b)->value=i;
                (*b)->leftChild = NULL;
                (*b)->rightChild = NULL;
                printf("[%i]",(*b)->value);
                return;
}

Note the changes to dereference the pointer pointer.

When you call this function, you'll need to take the address of your bst *:

insert(&b,5);

Answer 3

Well one problem is you're not typecasting your pointer.

The line:

b=malloc(sizeof(b));

Should be:

b=(bst*)malloc(sizeof(b));

Your code gives me an error when I compile it in gcc.

---

This is how to identify and fix errors in the future:

Testing in GDB:

Full code:

#include <malloc.h>
#include <stdio.h>

typedef struct node
{
    struct node *leftChild, *rightChild;
    int value;
} bst;

void insert(bst* b, int i)
{
  b=(bst*)malloc(sizeof(b));
                b->value=i;
                b->leftChild = NULL;
                b->rightChild = NULL;
                printf("[%i]",b->value);
                return;
}
main()
{
  bst* b;
  insert(b,5);
  printf("[%i]",b->value);
}

Compiled with

%g++ -g main.cc

Ran with

%gdb a.out

GDB commands:

b main.cc:211
run
print b
(output is: 0x0)
step
step
print b
(output is: 0x4f60010)
step
step
step
step
step
print b
(output is: 0x0)
quit

This clearly indicates that your variable is getting deallocated when the function leaves its scope.

Changing the code to:

#include <malloc.h>
#include <stdio.h>

typedef struct node
{
    struct node *leftChild, *rightChild;
    int value;
} bst;

void insert(bst* b, int i)
{
                b->value=i;
                b->leftChild = NULL;
                b->rightChild = NULL;
                printf("[%i]",b->value);
                return;
}
main()
{
  bst* b;
  b=(bst*)malloc(sizeof(bst));
  insert(b,5);
  printf("[%i]",b->value);
  free(b);
}

and rerunning gdb with the following commands:

b main.cc:21
run
s
(short for step)
print b
(output: 0x1aab010)
s
s
s
s
s
s
print b
(output: 0x1aab010)

Your problem is clearly the scope of the allocation. Moving the allocation to main fixes this.

Yay your program now works!

This should give you insight into how to use the debugger to solve these kinds of simple errors in the future.

---

Edit:

As one op pointed out, your underlying problem is that pointers passed to functions in c are treated as local objects, so when you exit the function, any allocated memory to single pointers is tossed in the bitbucket.

Double pointers allow you to actually allocate within functions, you just have to be careful to dereference them as necessary. So your working code could also be:

#include <malloc.h>
#include <stdio.h>

typedef struct node
{
    struct node *leftChild, *rightChild;
    int value;
} bst;

void insert(bst** b, int i)
{
                (*b)=(bst*)malloc(sizeof(bst));
                (*b)->value=i;
                (*b)->leftChild = NULL;
                (*b)->rightChild = NULL;
                printf("[%i]",(*b)->value);
                return;
}
main()
{
  bst* b;
  insert(&b,5);
  printf("[%i]",b->value);
  free(b);
}

Answer 4

The problem is that b in main points to an invalid memory. The b doesn't get changed by insert because insert uses a copy of the pointer. You have to options to solve this:

• Make "insert" take a pointer to pointer
• Allocate the memory before entering "insert"

Because the first one is harder to read (and understand), I'd prefer the second one. But it depends on you what variant you choose.

Memory allocation before insert:

typedef struct node
{
    struct node *leftChild, *rightChild;
    int value;
} bst;

void insert(bst* b, int i)
{
                // No malloc here
                b->value=i;
                b->leftChild = NULL;
                b->rightChild = NULL;
                printf("[%i]",b->value);
                return;
}
main()
{
  bst* b = (bst *)malloc(sizeof(bst));  // This line has changed
  insert(b,5);
  printf("[%i]",b->value);
}

The variant with a double pointer:

typedef struct node
{
    struct node *leftChild, *rightChild;
    int value;
} bst;

void insert(bst** b, int i)
{
                *b = (bst *)malloc(sizeof(bst));  // This line has changed
                (*b)->value=i;
                (*b)->leftChild = NULL;
                (*b)->rightChild = NULL;
                printf("[%i]", (*b)->value);
                return;
}
main()
{
  bst* b;
  insert(&b,5);  // Now b is changed
  printf("[%i]",b->value);
}

Side note 1: you also have the malloc() incorrect - you should put use sizeof(bst) instead of sizeof(b) as the size. This is because sizeof(b) == sizeof(bst *) == size of an address, which is almost certainly not what you want.

Side note 2: do not forget to call free(b) at the end to avoid memory leaks.

Side note 3: check that malloc() doesn't return NULL. A rare case but a good program should expect that.

Answer 5

Since C does pass-by-value for arguments, the pointer being referenced inside insert() is a copy of the original b. The memory gets allocated to the variable b inside the function, but not to the variable in the main()function.

for eg.

# In main
b<main> = 0xOrigLoc
b<insert> = undefined

# In insert (before malloc)
b<main> = 0xOrigLoc
b<insert> = 0xOrigLoc

# After Malloc
b<main> = 0xOrigLoc
b<insert> = 0xNewLoc

Notice how b<main> remains untouched. You are only tweaking the copy of b inside the function.

The solution is to use a pointer to a pointer as described by the previous solution.

Answer 6

Rather than change the value, return the new value of b

bst* insert(bst* b, int i)
{
    if (b == NULL)
    {
        bst* result = (bst*)malloc(sizeof(bst));
        result->value=i;
        result->leftChild = NULL;
        result->rightChild = NULL;
        printf("[%i]",b->value);
        return result;
    }

    if (i < b->value)
        b->left  = insert(b->left, i);
    else
        b->right = insert(b->right, i);
    return b;
}

int main()
{
  bst* b  = NULL;   // Initialise it to empty.
  b       = insert(b,5);
  printf("[%i]",b->value);
}