Beginning C BST implementation

Question

I'd really appreciate if I could get some feedback on the following code with regard to security, efficiency and possible uncaught errors. Personally I feel the printAndCleanString and friendlyLookup functions combined are very messy but I don't know how to fix them.

In particular I would love feedack on how to more cleanly and efficiently return strings.

#include <stdio.h>
#include <malloc.h>
#include <mem.h>
struct bstNode {
 int val;
 struct bstNode *left;
 struct bstNode *right;
};
void insert(struct bstNode **head, int val);
int lookup(struct bstNode **node, int val);
void printDFS(struct bstNode *head);
char *friendlyLookup(struct bstNode **node, int val);
void printAndCleanString(char *string);
int main() {
 struct bstNode *bstTree = NULL;
 insert(&bstTree, 8);
 insert(&bstTree, 5);
 insert(&bstTree, 98);
 insert(&bstTree, 2);
 insert(&bstTree, 15);
 insert(&bstTree, 65);
 insert(&bstTree, 15);
 printDFS(bstTree);
 printf("\n");
 printAndCleanString(friendlyLookup(&bstTree, 1));
 printAndCleanString(friendlyLookup(&bstTree, 65));
}
void insert(struct bstNode **head, int val) {
 if (*head == NULL) {
 *head = malloc(sizeof(struct bstNode));
 if (*head == NULL) {
 printf("malloc failed!");
 return;
 }
 (*head)->val = val;
 (*head)->left = NULL;
 (*head)->right = NULL;
 return;
 }
 if (val < (*head)->val) {
 return insert(&(*head)->left, val);
 } else {
 return insert(&(*head)->right, val);
 }
}
void printDFS(struct bstNode *head) {
 if (head->left != NULL) printDFS(head->left);
 printf("%d ", head->val);
 if (head->right != NULL) printDFS(head->right);
}
int lookup(struct bstNode **node, int val) {
 if (*node == NULL) {
 return -1;
 }
 if ((*node)->val == val) {
 return val;
 }
 if (val < (*node)->val) {
 return lookup(&(*node)->left, val);
 } else {
 return lookup(&(*node)->right, val);
 }
}
char *friendlyLookup(struct bstNode **node, int val) {
 int result = lookup(node, val);
 char resultString[256];
 char numberString[256];
 sprintf(numberString, "%d", val);
 if (result > -1) {
 sprintf(resultString, " is present in the bst\n");
 } else {
 sprintf(resultString, " is not present in the bst\n");
 }
 char *resultPointer = malloc(strlen(resultString) + strlen(numberString) + 1 * sizeof(char));
 if (resultPointer == NULL) {
 printf("Malloc error!");
 return NULL;
 }
 sprintf(resultPointer, "%s%s", numberString, resultString);
 return resultPointer;
}
void printAndCleanString(char *string) {
 printf(string);
 free(string);
}

Answer 1

1. #include <mem.h> should be properly #include <string.h>. The former is non-standard.
2. I prefer avoiding the duplication inherent in forward-declarations, so would put the definition before first use.
   Unless, of course, I'm writing a header-file.
3. Remember that your friendlyLookup() can fail. And test for that.
4. It's a bad idea to name the type in a sizeof like in *head = malloc(sizeof(struct bstNode));. Changing it to *head = malloc(sizeof **head); is more resilient to change, obviously correct, and even shorter.

5. There are a few viable strategies for handling failure:

   1. Ignoring it and hoping the program will crash. Even for toy-programs, that's extremely bad form.
   2. Deteting it and aborting the program with an error-message. Often acceptable when resources are exceeded.
   3. Fixing the failure. Often not possible, or at least not at that place.
   4. Reporting the failure to the caller and letting them deal with it. The preferred method, especially for library-code.

   You are instead doing a mixture: Printing an error-message (part of option 2) and then pretending you succeeded. That's a really bad combo.

6. Learn to love the ternary operator condition ? true-case : false-case. It would often simplify your code.

Applying some of the above:

void die(char* msg) {
 fprintf(stderr, "%s", msg);
 abort();
}
void insert(struct bstNode **head, int val) {
 if(!*head) {
 *head = malloc(sizeof **head);
 if(!*head)
 die("malloc failed!");
 **head = (struct bstNode){.val = val};
 return;
 }
 insert(val < (*head)->val ? &(*head)->left : &(*head)->right, val);
}

7. if (head->left != NULL) is exactly the same as if (head->left).

8. In friendlyLookup() you are copying one of two string-literals into a (far too big) array, just to copy it again. Why? Use a pointer.

   const char* resultString = result > -1 ? " is present in the bst\n" : " is not present in the bst\n";
   

9. Also, numberString is far too big, but whatever.
10. printAndCleanString is a curious name. If such a utility-function makes sense, it should be "free" instead of "clean".

11. If you want to output a string, don't give it as format-string to printf(), but as an argument. Make it:

    printf("%s", string);