Issue with allocating char pointer

Question

#pragma once
#define _CRT_SECURE_NO_WARNINGS

typedef struct Item
{
    char* msg;
} Item;

typedef struct TreeNode* link;
//typedef struct BSTNode* link;

struct TreeNode {
    Item msg; // the data
    link pLeft; // left subtree
    link pRight; // right subtree
};

link root;

link NEW(Item item, link left, link right);
void Delete(link p);
void BSTInit(void);
Item BSTSearch(link h, char* szSearchKey);
Item Search(char* szKey);
link BSTInsert(link h, Item item);
void Insert(Item item);
int count(link h);
int height(link h);
void BSTPrint(link h);\

#include"Tree.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>



static link head;
static Item NullItem = { NULL };


link NEW(Item item, link left, link right) {
    link pNew = (link)malloc(sizeof(*pNew));
    pNew->msg.msg = (char*)malloc(strlen(item.msg) + 1);
    strcpy(pNew->msg.msg, item.msg);
    pNew->pLeft = left;
    pNew->pRight = right;
    return(pNew);
}

void Delete(link p) {
    if (p == NULL) 
        return;
    Delete(p->pLeft); // recursively free left subtree
    Delete(p->pRight); // recursively free right subtree
    free(p); // free current node
}

void BSTInit(void) {
    head = NEW(NullItem, NULL, NULL); // initializing empty tree
}

Item BSTSearch(link h, char* szSearchKey) {
    int rc;
    if (h == NULL) return(NullItem); // Got to end & not found
    rc = strcmp(szSearchKey, h->msg.msg);
    if (rc == 0) return(h->msg);// Found it
    if (rc < 0) return(BSTSearch(h->pLeft, szSearchKey));
    else return(BSTSearch(h->pRight, szSearchKey));
}

Item Search(char* szKey) 
{ 
    return(BSTSearch(head, szKey)); 
}

link BSTInsert(link h, Item item) {
    int rc;
    if (h == NULL) return(NEW(item, NULL, NULL)); // insert pt
    rc = strcmp(item.msg, h->msg.msg); // Go left or right? // issue with this line
    if (rc < 0) {
        h->pLeft = BSTInsert(h->pLeft, item);
    }
    else {
        h->pRight = BSTInsert(h->pRight, item);
    }
    return(h); // pointer to (new/existing) child
}

void Insert(Item item)
{
    head = BSTInsert(head, item);
}


int count(link h) {
    if (h == NULL) return(0);
    return(count(h->pLeft) + count(h->pRight) + 1);
}

int height(link h) {
    int iLeftH, iRightH;
    if (h == NULL) 
        return(-1);
    iLeftH = height(h->pLeft);
    iRightH = height(h->pRight);
    if (iLeftH > iRightH) {
        return(iLeftH + 1);
    }
    else {
        return(iRightH + 1);
    }
}

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#include"Tree.h"
#include"RandomChar.h"



int main()
{
    srand((unsigned)time(NULL));
    int rand_num = rand() % (20 + 1 - 11) + 11;  // random amount of times letters generated
   
    BSTInit();


    for (int i = 0; i < rand_num; i++)
    {
        char newChar = RandomChar();
        Item newItem;
        newItem.msg = malloc(sizeof(char) * 2);  // allocate memory for the character and the null terminator
        strcpy(newItem.msg, &newChar);  // copy the character to the allocated memory
        Insert(newItem);
    }

    printf("Printing tree in alphabetical order...\n");
    BSTPrint(root);
    Delete(root);

    return 0;
}

Having issues with the NEW function as char is not allocating and returns NULL. I am searching binary tree with each node that stores a randomly generated char. This char is inserted into the tree using strcmp to adjust the order. Than I have to print the tree in that order. The code is not compiling and getting error pNew returning NULL but I am using strcpy to ensuring this is not happening.

Answer 1

This statement within the function BSTInit

head = NEW(NullItem, NULL, NULL);

invokes undefined behavior.

The variable NullItem is declared like

static Item NullItem = { NULL };

That is its data member msg is a null pointer.

So within the function NEW there is used the null pointer in calls of the string functions strlen and strcpy

pNew->msg.msg = (char*)malloc(strlen(item.msg) + 1);
strcpy(pNew->msg.msg, item.msg);

The function BSTInit is redundant because as the pointer head declared with static storage duration is already initialized as a null pointer and initially it shall be a null pointer.

And this call of strcpy in main

char newChar = RandomChar();
//...
strcpy(newItem.msg, &newChar)

also invokes undefined behavior because you are trying to copy a single character without following terminating zero character '\0' as a string.

Also due to this memory allocation within the for loop in main

for (int i = 0; i < rand_num; i++)
{
    char newChar = RandomChar();
    Item newItem;
    newItem.msg = malloc(sizeof(char) * 2); 
    //...

the program produces numerous memory leaks.

Pay attention to that it is a bad idea to declare the pointer head as a file scope variable and when functions depend on global variables.