C: binary trees, memory allocation

Question

So I'm trying to build a binary tree in C using structs and all that jazz. So far, I've got the following:

#include <stdio.h>
#include <string.h>
#include <stdarg.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include <signal.h>

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

node *top = NULL;

static node *addNode(int e, node *n);
static void printTree(node *n);

static node *addNode(int e, node *n) {
    if(top == NULL) {
        top = malloc(sizeof(node));
        top->value = e;
        top->left = NULL;
        top->right = NULL;
        return top;
    } else if (n != NULL) {
        if(e <= n->value) {
            if(n->left == NULL) {
                n->left = addNode(e, n->left);
            } else {
                (void) addNode(e, n->left); 
            }
        } else {
            if(n->right == NULL) {
                n->right = addNode(e, n->right);
            } else {
                (void) addNode(e, n->right);
            }
        }
    } else if(n == NULL) {
        n = malloc(sizeof(node));
        n->value = e;
        n->left = NULL;
        n->right = NULL;
        return n;
    }
    return n;
}

static void printTree(node *n) {
    if(n != NULL) {
        fprintf(stdout, "%d, ", n->value);
        if(n->left != NULL) {
            printTree(n->left);
        }
        if(n->right != NULL) {
            printTree(n->right);
        }
    }
}

int main(int argc, char **argv) {
        addNode(1, top);
        addNode(2, top);
        addNode(0, top);
        addNode(3, top);
        printTree(top);
return 0;
}

It's missing stuff like about everything other than adding nodes and printing the tree, but that's where I have questions already. What I do get is some odd behaviour in the addNode function: Originally, I had the first if clause set up as

if(n == NULL) {
    n = malloc(sizeof(node));
    n->value = e;
    n->left = NULL;
    n->right = NULL;
    return n;
}

Which didn't work out at all - no new nodes were created due to that. The way it is now, it's working out the way it has to - and I don't really understand why it behaves like that. When I call the addNode function for the first time, I'm giving it the top pointer as a parameter anyways, so it should check if it's null (which it should be at that point) and should just allocate some memory for it. It does not happen, though. And I don't get why.

Answer 1

Several points here. First let start by details: your printTree() is too complicated. As you check for NULL value when entering the function you don't have to check it again for left/right:

void printTree(node *n) {
  if (n == NULL) { return; }  // just leave
  printTree(n->left);
  printf("%d\n", n->value);
  printTree(n->right);
}

Note that the order of printing value, left and right will change the output. In this example it will be printed from low to high values.

Now for your addNode() you don't need a global top value. You give the top to your function and get the new one with returned value (top = addNode(val, top);. Having this global value just can lead to bad code when mixing n and top access. And the function can be more simple:

node *addNode(int val, node *n) {
  if (n == NULL) {  // just allocate a new one
    n = malloc(sizeof(node));  // add check for failure here, of course
    n->left = n->right = NULL; // it is a leaf, no child
    n->value = val;
    return(n);  // return the node for caller
  }
  // ok, we are on a node, check on which side we need to insert
  if (val < n->value) {
    // to the left: it may be replaced (if created)
    n->left = addNode(val, n->left);
  } else {
    // same, for right
    n->right = addNode(val, n->right);
  }
  // return the node so that top=addNode(val,top) always works
  return(n);
}

You can prevent passing+getting node using a pointer to the node, but then you'll have to well understand dereferencing pointers. It could be:

void addNode(int val, node **n) {
  if (*n == NULL) {  // just allocate a new one
    *n = malloc(sizeof(node));  // add check for failure here, of course
    (*n)->left = (*n)->right = NULL; // it is a leaf, no child
    (*n)->value = val;
    return;  // return, the node 'n' is still modified
  }
  // ok, we are on a node, check on which side we need to insert
  if (val < (*n)->value) {
    // to the left: it may be replaced (if created)
    (*n)->left = addNode(val, (*n)->left);
  } else {
    // same, for right
    (*n)->right = addNode(val, (*n)->right);
  }
  // leave function (return not needed), node unchanged
  return;
}

Then you will call this function this way:

int main(void) {
  node *top = NULL;  // must be initialized

  addNode(3, &top);
  addNode(1, &top);
  addNode(5, &top);
  printNode(top);
  (…)

Answer 2

You need to assign the first node to top.

int main(int argc, char **argv) {
    top = addNode(1, top);
    addNode(2, top);
    addNode(0, top);
    addNode(3, top);
    printTree(top);
    return 0;
}

With your original if clause, top was not getting updated. You were just returning n.