C library implementing binary trees

Question

This is my first attempt at writing a library in C. I have only included tree creation and in-order traversal function for now, but will expand to have more functions soon. I have three files, tree.h, tree.c and test.c. How can I improve code quality, what are your suggestions? My main concerns are:

1. Optimizations - Is my code sufficiently optimized and is any more optimization possible?
2. Memory leaks - Is there any scope for memory leaks?
3. Readability

Below is the code for tree.h

#ifndef TREE_H
#define TREE_H

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define null NULL

#endif

typedef struct tree_node {
  int val;
  struct tree_node *left, *right;
} TreeNode;
typedef struct tree {
  TreeNode *root;
} Tree;

static int count_nodes_in_string(char *);
static char** word_break(char *string, int n);
static int convert_to_integer(char *);
static char *convert_to_string(int val);
static TreeNode *create_node(int);
static TreeNode *make_tree_helper(char **, int, int);
static void inorder_helper(TreeNode *, char **);
static void delete_helper(TreeNode *);

char* inorder(Tree *);
Tree *makeTree(char *);
void deleteTree(Tree *);

The code for tree.c

#include "tree.h"
#define delim ' '

static int count_nodes_in_string(char *string) {
  int index = 0, count = 0;
  while(string[index] != '\0') {
    if(string[index] == delim) {
      count++;
    }
    index++;
  }
  return count + 1;
}

static char** word_break(char *string, int number) {
  int index = 0, count = 0, prev = 0;
  char **words = (char **)malloc(sizeof(char*) * number);

  while(string[index] != '\0') {
    if(string[index] == delim) {
      words[count] = (char *)malloc(sizeof(char) * (index - prev + 1));
      strncpy(words[count], string + prev, index - prev);
      words[count][index - prev] = '\0';
      prev = index + 1;
      count++;
    }
    index++;
  }
  //For last word.
  words[count] = (char *)malloc(sizeof(char) * (index - prev + 1));
  strncpy(words[count], string + prev, index - prev);
  words[count][index - prev] = '\0';
  return words;
}

static int convert_to_integer(char *number) {
  int index = 0, result = 0;
  while(number[index] != '\0') {
    result = result * 10 + number[index] - '0';
    index++;
  }
  free(number);
  return result;
}

static char *convert_to_string(int val) {
  int digits = log10(val) + 1, rem;
  int index = digits - 1;
  char *number_to_string = malloc((digits + 1) * sizeof(char));
  if(number_to_string == null) {
    printf("Error: Unable to allocate memory.");
    exit(1);
  }
  while(val > 0) {
    number_to_string[index] = (val % 10 + '0');
    val = val / 10;
    index--;
  }
  number_to_string[digits] = ' ';
  return number_to_string;
}


static TreeNode *create_node(int val) {
  TreeNode *node = malloc(sizeof(TreeNode));
  if(node == null) {
    printf("Error: Unable to allocate memory.");
    exit(1);
  }
  node->val = val;
  node->right = node->left = null;
  return node;
}

static TreeNode *make_tree_helper(char **words, int n, int i) {
  if(i >= n) {
    return null;
  }
  if(strcmp(words[i], "N") == 0) {
    return null;
  }
  TreeNode *root = create_node(convert_to_integer(words[i]));
  root->left = make_tree_helper(words, n, 2 * i + 1);
  root->right = make_tree_helper(words, n, 2 * i + 2);
  return root;
}

static void inorder_helper(TreeNode *root, char **inorder_string) {
  if(root) {
    inorder_helper(root->left, inorder_string);
    char *converted_integer = convert_to_string(root->val);
    if(*inorder_string == null) {
      *inorder_string = strdup(converted_integer);
    }
    else {
      strcat(*inorder_string, converted_integer);
    }
    free(converted_integer);

    inorder_helper(root->right, inorder_string);
  }
  return;
}

static void delete_helper(TreeNode *root) {
  if(root) {
    delete_helper(root->left);
    delete_helper(root->right);
    free(root);
  }
  return;
}


char* inorder(Tree *tree) {
  char *inorder_string = null;
  inorder_helper(tree->root, &inorder_string);
  return inorder_string;
}

Tree *makeTree(char *string) {
  Tree *tree = malloc(sizeof(Tree));
  if(tree == null) {
     printf("Error: Unable to allocate memory.");
     exit(1);
  }
  int nodes = count_nodes_in_string(string);
  char **words = word_break(string, nodes);
  tree->root = make_tree_helper(words, nodes, 0);
  return tree;
}

void deleteTree(Tree *tree) {
  delete_helper(tree->root);
  free(tree);
  tree = null;
}

And the code for test.c

#include <stdio.h>
#include <string.h>
#include "tree.h"

static unsigned test_tree_lib(const char *, int, char *, char *);

#define TEST_BINARY_TREE(input, expected) failures += test_tree_lib(__FILE__, __LINE__, input, expected)

static unsigned test_tree_lib(const char *file, int line, char *input, char *expected) {
  Tree *tree = makeTree(input);
  char *inorder_traversal = inorder(tree);
  int result = strcmp(inorder_traversal, expected);
  printf("%s\n", inorder_traversal);
  free(inorder_traversal);
  deleteTree(tree);
  return result == 0;
}

int main() {
  unsigned failures = 0;
  unsigned test = 3;

  char test1[] = "1 2 3 4";
  TEST_BINARY_TREE(test1, "4 2 1 3 ");
  char test2[] = "4 2 6 1 3 5 7";
  TEST_BINARY_TREE(test2, "1 2 3 4 5 6 7 ");
  char test3[] = "50 30 60 5 20 45 70 N N N N N N 65 80";
  TEST_BINARY_TREE(test3, "5 30 20 50 45 60 65 70 80 ");

  printf("\n---------------- Tests completed ----------------\n");
  printf("\n---------------- Total tests : %u ---------------\n", test);
  printf("\n-------------- Successful tests : %u ------------\n", failures);
  return failures > 0;
}

Answer 1

Answers to Questions:

1. Optimizations - Is my code sufficiently optimized and if any more optimization is possible.

Optimization is the last thing to worry about once the code is written properly and working as expected. Most of the optimization can accomplished be by using the -O3 compiler switch; it generally does a better job of optimization than optimizing code by hand.

2. Memory leaks - Is there any scope for memory leaks.

Whether or not there are memory leaks is academic at this time, there is a buffer overflow problem in the function static void inorder_helper(TreeNode* root, char** inorder_string). A string allocated by strdup() will not contain enough space for additional strings to be concatenated. The entire in-order traversal needs to be redesigned and or reimplemented.

3. Readability

The readability is fair, the variable and function names are good. The readability could be improved by adding some vertical spacing between the functions and between logic blocks within the functions.

Proper Header Files for a Library

Only include in the header file what is necessary for files accessing the library to compile properly. Right now the header file contains things that aren't necessary and in some cases may cause problems for linking or compiling. The file tree.c should contain the header files that are currently included by tree.h. The only code tree.h should contain are the definitions of the tree and the 3 global entry point functions.

#ifndef TREE_H
#define TREE_H

typedef struct tree_node {
    int val;
    struct tree_node* left, * right;
} TreeNode;

typedef struct tree {
    TreeNode* root;
} Tree;

char* inorder(Tree*);
Tree* makeTree(char*);
void deleteTree(Tree*);

#endif

The static declarations for all the functions aren't necessary for code utilizing the library and could collide with functions in the modules that are including the library.

The lowercase null definition is only necessary in tree.c and should be declared there, although I would really recommend that you just stick with the original definition of NULL.

The current include guard #ifndef TREE_H is not effective and will allow most of the file to be included multiple times.

Answer 2

Here's a couple of lines with numerous issues:

  words[count] = (char *)malloc(sizeof(char) * (index - prev + 1));
  strncpy(words[count], string + prev, index - prev);

• sizeof (char) yields 1, since a char always needs exactly one char to store it. Multiplying by 1 is pointless clutter.
• malloc() returns a void*, which can be assigned to any pointer type without adding an unnecessary cast.
• strncpy requires the destination to point to valid storage. Passing a null pointer (as returned by malloc() when it can't satisfy our request) results in undefined behaviour. If you're lucky, the program will simply crash, but much more harmful results are possible.

We can make that much better:

  words[count] = malloc(index - prev + 1);
  if (words[count]) {
      strncpy(words[count], string + prev, index - prev);

These same issues occur throughout the code. I recommend fixing them and bringing the result back for further review.