Ternary Search Tree Insertion

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

// Ternary search tree 
struct TreeNode
{
    char data;
    int terminate;
    struct TreeNode *left;
    struct TreeNode *equal;
    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)
    {
        printf("Memory Overflow to create new tree node\n");
        // Memory overflow
        exit(0);
    }
    node->left = NULL;
    node->equal = NULL;
    node->right = NULL;
    node->data = data;
    node->terminate = 0;
    return node;
}
// Print the all words using recursion
void printWords(struct TreeNode *root, char *output, int depth)
{
    if (root != NULL)
    {
        // First traverse the left subtree 
        printWords(root->left, output, depth);

        // Store the character of this node 
        output[depth] = root->data;

        if (root->terminate)
        {
            // Include termination character
            output[depth + 1] = '\0';

            // Display word
            printf(" %s\n", output);
        }
        // Visit equal (middle) subtree
        printWords(root->equal, output, depth + 1);
        // Visit left subtree
        printWords(root->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;
    }
}
// Handles the request of printing tree elements
void traverseTST(struct TreeNode *root)
{
    if (root == NULL)
    {
        return;
    }
    // Find height of tree
    int h = treeHeight(root) + 1;

    // Use to collect word character
    char output[h];
    // Print all words
    printWords(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->equal = insert(node->equal, 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 searchElement(struct TreeNode *root, char *word)
{
    if (root == NULL)
    {
        return 0;
    }
    else if ( *word < root->data)
    {
        return searchElement(root->left, word);
    }
    else if ( *word > root->data)
    {
        return searchElement(root->right, word);
    }
    else
    {
        if ( *(word + 1))
        {
            // When word not empty
            return searchElement(root->equal, word + 1);
        }
        else
        {
            // returns status to terminate word
            return root->terminate;
        }
    }
}
// Handles the request of search word
void searchTreeNode(struct TreeNode *root, char *word)
{
    printf("\n Given : [%s] \n", word);
    if (searchElement(root, word) == 1)
    {
        printf(" Found\n");
    }
    else
    {
        printf(" Not Found\n");
    }
}
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);
    // Test Cases
    searchTreeNode(tree->root, "milk");
    searchTreeNode(tree->root, "fee");
    searchTreeNode(tree->root, "milks");
    return 0;
}

input

 Ternary search tree
 co
 code
 fee
 feel
 milk
 run

 Given : [milk]
 Found

 Given : [fee]
 Found

 Given : [milks]
 Not Found