Ternary Search Tree Deletion

// C program for
// Ternary Search Tree Deletion
#include <stdio.h>
#include <stdlib.h>

// Ternary search tree Node
struct TreeNode
{
	char data;
	int terminate;
	struct TreeNode *left;
	struct TreeNode *eq;
	struct TreeNode *right;
};
struct TernarySearchTree
{
	struct TreeNode *root;
};
// Create and return new tree
struct TernarySearchTree *newTree()
{
	// Create a dynamic node
	struct TernarySearchTree *tree = 
      (struct TernarySearchTree *) malloc(sizeof(struct TernarySearchTree));
	if (tree != NULL)
	{
		tree->root = NULL;
	}
	else
	{
		printf("Memory Overflow to Create tree Tree\n");
		exit(0);
	}
	// Return new tree
	return tree;
}
// Create new node of tree
struct TreeNode *newTreeNode(char data)
{
	struct TreeNode *node = 
      (struct TreeNode *) malloc(sizeof(struct TreeNode));
	if (node == NULL)
	{
		// Memory overflow
		exit(0);
	}
	node->left = NULL;
	node->eq = NULL;
	node->right = NULL;
	node->data = data;
	node->terminate = 0;
	return node;
}
// A recursive function to traverse Ternary Search Tree 
void traverseTSTUtil(struct TreeNode *node, char *output, int depth)
{
	if (node != NULL)
	{
		// First traverse the left subtree 
		traverseTSTUtil(node->left, output, depth);
		// Store the character of this node 
		output[depth] = node->data;
		if (node->terminate)
		{
			output[depth + 1] = '\0';
			printf(" %s\n", output);
		}
		// Traverse the subtree using equal pointer (middle subtree) 
		traverseTSTUtil(node->eq, output, depth + 1);
		// Finally Traverse the right subtree 
		traverseTSTUtil(node->right, output, depth);
	}
}
// Calculate height of tree
int treeHeight(struct TreeNode *node)
{
	if (node != NULL)
	{
		// Find height of subtree using recursion
		int a = treeHeight(node->left);
		int b = treeHeight(node->right);
		// Returns the height of largest subtree 
		if (a > b)
		{
			return a + 1;
		}
		else
		{
			return b + 1;
		}
	}
	else
	{
		return 0;
	}
}
void traverseTST(struct TreeNode *root)
{
	if (root == NULL)
	{
		return;
	}
	int h = treeHeight(root) + 1;
	char output[h];
	traverseTSTUtil(root, output, 0);
}
// Function to insert a new word in a Ternary Search Tree 
struct TreeNode *insert(struct TreeNode *root, char *word)
{
	struct TreeNode *node = root;
	if (root == NULL)
	{
		node = newTreeNode( *word);
	}
	if (( *word) < node->data)
	{
		node->left = insert(node->left, word);
	}
	else if (( *word) > node->data)
	{
		node->right = insert(node->right, word);
	}
	else
	{
		if ( *(word + 1))
		{
			node->eq = insert(node->eq, word + 1);
		}
		else
		{
			node->terminate = 1;
		}
	}
	return node;
}
// Handles the request of add new node
void addNode(struct TernarySearchTree *tree, char *word)
{
	tree->root = insert(tree->root, word);
}
int countSiblings(struct TreeNode *node)
{
	int count = 0;
	if (node->left != NULL)
	{
		count++;
	}
	if (node->right != NULL)
	{
		count++;
	}
	if (node->eq != NULL)
	{
		count++;
	}
	return count;
}
struct TreeNode *deleteWord(struct TreeNode *node, char *word)
{
	if (node == NULL)
	{
		printf(" Delete word not found \n");
		// When delete node not exist
		return NULL;
	}
	int child = countSiblings(node);
	if ( *word < node->data)
	{
		node->left = deleteWord(node->left, word);
	}
	else if ( *word > node->data)
	{
		node->right = deleteWord(node->right, word);
	}
	else
	{
		if ( *(word + 1))
		{
			// When word not empty
			node->eq = deleteWord(node->eq, word + 1);
		}
		else if (node->terminate == 1)
		{
			if (child > 0)
			{
				// In case child node exist of deleted word
				node->terminate = 0;
			}
			else
			{
				free(node);
				return NULL;
			}
		}
	}
	if (child != countSiblings(node) && child == 1 && node->terminate == 0)
	{
		// When need to remove node
		free(node);
		return NULL;
	}
	return node;
}
int main()
{
	struct TernarySearchTree *tree = newTree();
	// Add word
	addNode(tree, "feel");
	addNode(tree, "fee");
	addNode(tree, "run");
	addNode(tree, "milk");
	addNode(tree, "co");
	addNode(tree, "code");
	printf(" Ternary search tree\n");
	traverseTST(tree->root);
	// Case A
	char *word = "fee";
	printf("\n Delete word : %s \n", word);
	tree->root = deleteWord(tree->root, word);
	printf(" Ternary search tree\n");
	traverseTST(tree->root);
	// Case B
	word = "code";
	printf("\n Delete word : %s \n", word);
	tree->root = deleteWord(tree->root, word);
	printf(" Ternary search tree\n");
	traverseTST(tree->root);
	// Case C
	word = "milks";
	printf("\n Delete word : %s \n", word);
	tree->root = deleteWord(tree->root, word);
	printf(" Ternary search tree\n");
	traverseTST(tree->root);
	// Case D
	word = "feel";
	printf("\n Delete word : %s \n", word);
	tree->root = deleteWord(tree->root, word);
	printf(" Ternary search tree\n");
	traverseTST(tree->root);
	return 0;
}

input

 Ternary search tree
 co
 code
 fee
 feel
 milk
 run

 Delete word : fee
 Ternary search tree
 co
 code
 feel
 milk
 run

 Delete word : code
 Ternary search tree
 co
 feel
 milk
 run

 Delete word : milks
 Delete word not found
 Ternary search tree
 co
 feel
 milk
 run

 Delete word : feel
 Ternary search tree
 co
 milk
 run