Designing a binary tree structure from scratch in C

Question

I'm a beginner and self learning programming students. While learning binary tree data types, for the sake of understanding graph theory and other interesting programming problems, I've writen the below implementation. Would you please suggest if there's anything wrong or either this can be improved.

It may seem reinventing the wheel, as there's a nice STL in C++, but I do implement data structure and algos from scratch for the sake of a better understanding and visualization for me

Here's my code, and thanks in advance

#include <stdio.h>
#include <stdlib.h> 
typedef struct tree {
 int value;
 struct tree *left_child;
 struct tree *right_child;
} bin_tree; 
void create_tree(int value, bin_tree **root);
void print_tree(bin_tree *root);
void free_mem(bin_tree *root);
int main() {
 bin_tree *root;
 root = (bin_tree *) malloc (sizeof(bin_tree));
 root = NULL;
 int val;
 while (scanf("%d", &val) != EOF) {
 create_tree(val, &root);
 }
 printf("root : %d\n", root->value);
 print_tree(root);
 free_mem(root);
 //printf("root: %d\n", root->value);
 return 0;
 }
void create_tree(int val, bin_tree **root) {
 if (*root == NULL) {
 bin_tree *cache = (bin_tree *) malloc(sizeof(bin_tree));
 cache->value = val;
 cache->left_child = NULL;
 cache->right_child = NULL;
 *root = cache;
 }
 /*this tree is built avoiding duplicates*/
 else if(val < (*root)->value){ create_tree(val, &(*root)->left_child);}
 else if(val > (*root)->value){ create_tree(val, &(*root)->right_child);}
 }
 void print_tree(bin_tree *root) {
 if (root != NULL) {
 print_tree(root->left_child);
 print_tree(root->right_child);
 printf("%d ", root->value);
 }
 }
 void free_mem(bin_tree *root) {
 if (root) {
 free_mem(root->left_child);
 free_mem(root->right_child);
 free(root);
 }
 }

• syb0rg: "there's a nice STL in C++": C != C++
• ph03n1x: Yes I know the difference :)
• pm100: yes - it is a good idea to do this, its a great learning experience

Answer 1

Here are some things that may help you improve your code.

Don't leak memory

The main routine begins with these two curious lines of code:

root = (bin_tree *) malloc (sizeof(bin_tree));
root = NULL;

That's a guaranteed memory leak because we no longer have any way to refer to the memory allocated by malloc. Since your create_tree function will automatically allocate space for the root node, I'd change that to this, combining declaration and initialization:

bin_tree *root = NULL;

Check return values and handle errors

The code calls malloc but never checks for error return values. This is a serious problem that must be addressed. Also, scanf can return EOF if there was an error, but that condition is neither checked nor handled.

To be more precise, the way that the underlying operating system lets a program know that it cannot allocated the requested memory is by returning NULL from a call to malloc. Robust programs should always check for that condition before using the returned value as a pointer or they will risk a crash by dereferencing a NULL pointer.

Similarly, scanf returns the number of arguments successfully scanned. In your case it should be 1 because each call is scanning one integer value. If it's anything other than 1, it's an indication of a problem that should probably be handled gracefully by the program, perhaps by emitting a message to the user that only integer values are allowed and asking again.

Use "in-order" tree traversal

The binary tree you've constructed maintains the order of entries, so to take advantage of this, we should use in-order. It's as simply as changing the order of two lines of code so the print_tree code looks like this:

void print_tree(bin_tree *root) {
 if (root != NULL) {
 print_tree(root->left_child);
 printf("%d ", root->value);
 print_tree(root->right_child);
 }
}

So for example, when I feed the program this input:

10 5 33 2 18 17 15 20 22 1 8

The program then constructs this tree:

tree diagram

And an in-order traversal produces this output:

1 2 5 8 10 15 17 18 20 22 33

Put each statement on a single line

It detrimental to the readability of your code to put multiple things one the same line. So instead of this:

else if(val < (*root)->value){ create_tree(val, &(*root)->left_child);}

I would recommend writing this:

else if (val < (*root)->value) { 
 create_tree(val, &(*root)->left_child);
}

Omit return 0

When a C or C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no need to put return 0; explicitly at the end of main.

Note: when I make this suggestion, it's almost invariably followed by one of two kinds of comments: "I didn't know that." or "That's bad advice!" My rationale is that it's safe and useful to rely on compiler behavior explicitly supported by the standard. For C, since C99; see ISO/IEC 9899:1999 section 5.1.2.2.3:

[...] a return from the initial call to the main function is equivalent to calling the exit function with the value returned by the main function as its argument; reaching the } that terminates the main function returns a value of 0.

For C++, since the first standard in 1998; see ISO/IEC 14882:1998 section 3.6.1:

If control reaches the end of main without encountering a return statement, the effect is that of executing return 0;

All versions of both standards since then (C99 and C++98) have maintained the same idea. We rely on automatically generated member functions in C++, and few people write explicit return; statements at the end of a void function. Reasons against omitting seem to boil down to "it looks weird". If, like me, you're curious about the rationale for the change to the C standard read this question. Also note that in the early 1990s this was considered "sloppy practice" because it was undefined behavior (although widely supported) at the time.

So I advocate omitting it; others disagree (often vehemently!) In any case, if you encounter code that omits it, you'll know that it's explicitly supported by the standard and you'll know what it means.

• ph03n1x: Nice and precise answer @Edward. "Check return values and handle errors" please clear this point. As far I've read C codes I'vent found any error handling [I've scanty of knowledge and experience] so please clear me this point.
• Edward: I've added some explanation to my answer that I hope adequately addresses those points.
• ph03n1x: yes brother I've got it

Answer 2

1. Cast not needed.

   // root = (bin_tree *) malloc (sizeof(bin_tree));
   root = malloc (sizeof(bin_tree));
   

2. Allocate to the size of the de-reference variable, not to a type. Easier to code, less chance of error, easier to review, easier to maintain.

   // root = malloc (sizeof(bin_tree));
   root = malloc(sizeof *root);
   

3. When checking the return value, do not compare against one of a number of bad return values, compare against the desired one. With original code, a return value of 0 (due to non-numeric input) would cause an infinite loop. Robust code would handle the unexpected return value of 0 as an error.

   // while (scanf("%d", &val) != EOF) {
   // ...
   // }
   int cnt; 
   while ((cnt = scanf("%d", &val)) == 1) {
    ...
   }
   if (cnt != EOF) {
    fprintf(stderr, "Unexpected return value %d\n", cnt);
    return -1;
   } 
   

4. Formatting is inconsistent. Use an automatic formatter. Avoid manual formatting.

5. When the pointed-to data is not changed, use const. This allows for more compiler optimizaitons and lets users know the data is not changed.

   // void print_tree(bin_tree *root) {
   void print_tree(const bin_tree *root) {
   

6. I'd expect a different print order

    // print_tree(root->left_child);
    // print_tree(root->right_child);
    // printf("%d ", root->value);
    print_tree(root->left_child);
    printf("%d ", root->value);
    print_tree(root->right_child);
   

7. Minor: Not a fan of hanging spaces at the end of a line. They are hard to notice. Suggest:

    // printf("%d ", root->value);
    printf(" %d", root->value);
   

8. Inconsistent style. root != NULL vs. root. Suggest using the simpler one throughout.

   //void print_tree(bin_tree *root) {
   // if (root != NULL) {
   //void free_mem(bin_tree *root) {
   // if (root) {
   void print_tree(bin_tree *root) {
    if (root) {
   void free_mem(bin_tree *root) {
    if (root) {
   

9. Debug tip. In C, memory management is a pain. Zeroing free data has 2 advantages: it tends to more quickly show access errors of free'd data and from a security standpoint, clearing buffers is a good idea.

    free_mem(root->left_child);
    free_mem(root->right_child);
    memset(root, 0, sizeof *root); // add
    free(root);
   

• Edward: Strictly speaking, NULL is not required to have the value 0 so while your suggestion #9 is still good and still valid, a conforming C implementation might not necessarily interpret the zeroed memory as a NULL pointer. It is still a good idea from a security aspect, and is going to be interpreted as a NULL pointer on most platforms. See this question for details.
• chux: @Edward Strictly speaking, the question is not if the pointer has the value of NULL, the question is does (root) always have the same result as (root != NULL) - it does. if (root) causes a compare against 0 and (root == 0) leads to (root == (void *) 0). Both 0 and NULL cast to void* are null pointers, even if they have different values. Both will compare unequal to a pointer to any object or function. C11 §6.3.2.3 3
• chux: @Edward But finer idea supporting your point : a zero'd memory may not be interpreted as a null pointer if that pointer is not a void*. A zero'd memory interpreted as a void* is a null pointer, even if that is a different bit pattern than (void*)NULL.
• Edward: I was only referring to point #9. As mentioned here, in comments, int p == 0 && (bin_tree) p != 0 is permitted to be false because a null pointer does not have to map to 0.
• chux: @Edward I think you mean (bin_tree *) p (add *). And "because a pointer of a all 0 bits need not be a null pointer". This I agree, per spec, but have never encountered. I have encountered NULL being a pointer of bits not all zero.

Answer 3

For a self learning beginner you're doing pretty good.

Try to keep your indentation a little more consistent.

Memory Leaks You have several places in your program where you are leaking memory. The first is

 root = (bin_tree *) malloc (sizeof(bin_tree));
 root = NULL; 

There is no free(root); before assigning NULL to root. You should probably just have root = NULL; here, since you immediately throw away what you malloc().

In free_mem() you should traverse the whole tree to free all the memory before freeing the top level.

Travers the whole tree
In both print_tree() and free_mem() you are only affecting the top level, you need to traverse the tree to either print or free the nodes.

• ph03n1x: well when I directly paste from my editor to the stackexchange block for code the indentation goes disarranged. Any recommendation please ?
• pacmaninbw: Try to fix it. Just paste whole source from your IDE into edit box, then select it all (shift+[page]up/down), and Ctrl+K to make it "code formatted". It should then looks in the same way, as in your IDE (check preview before posting).