Ternary search trie insert function issues

Question

So I'm trying to make a Ternary search trie. Right now, I'm only working on the insert function. I have understood the basic idea of a ternary search trie online. I know that one root node has 3 leaves, and if the character comes before the root, it goes to the left, after - right and if it matches the root, it goes to the middle leaf. So my main objective is to make a program that can suggest words for miss-spelled user entered words. But at the moment I am just working on making the ternary search trie. I use the trie to make a dictionary using which I check user entered words to suggest the next best alternative. But right now, just working on inputting some characters into the ternary trie and when I display it should display it in order. I am not 100% sure of my logic regarding the middle leaves. Now my program, when run, give me some garbage unlimited values somehow related to the last character entered. I don't know where I've gone wrong. Could someone please point out where I have made my mistake? Also, could you please tell me if any of the logic I've written is wrong? I mean, you don't have to give me the code or anything as I feel I am capable of doing it myself once I understand where I've gone wrong, but if someone could just help me find my mistakes, it would help me a lot!

The WHOLE code :

#include <stdio.h>
#include <stdlib.h>  //Because usage of malloc gives warnings without this header
typedef struct tstree
{
    struct tstree *lokid;
    struct tstree *hikid;
    struct tstree *eqkid;
    char letter;
}node;
node *head = NULL;
int count = 0;
int insert(char x, node **head)
{
    if (*head==NULL)            //If it's the first element
    {
        *head = malloc(sizeof(node));   
        (*head)->letter = x;
        count++;            
        (*head)->lokid = (*head)->hikid = (*head)->eqkid = NULL;            //Assign all 3 to null initially
    }
    else if ((*head)->letter == x)          //If equal, insert below
    insert(x , &((*head)->eqkid) );
    else if ((*head)->letter > x)   //If inserted char comes before current val, insert to left
    insert(x,&(*head)->lokid);
    else
    insert(x,&(*head)->hikid);              //Else to the right
    return 0;
}
void display(node *head)
{
    if(head)
    {
        display(head->lokid);               //print in infix order
        printf("%c ",head->letter);
        display(head->hikid);
    }
    //return 0;
}
int main()
{   
    int op;
    char num;
    printf("\nWelcome Fabiz. Hope it meets your expectations!\n");
    while(1)
    {
        printf("\n1. To insert an element\n2. Display the tree\n3. Exit\nOption :");
        scanf("%d",&op);
        switch(op)
        {
            case 1:
            {
                system("clear");
                printf("\nEnter the element : ");
                scanf(" %c",&num);
                insert(num,&head);
                break;
            }
            case 2:
            {
                system("clear");
                if(count == 0)
                printf("\nEmpty tree\n");
                else
                {
                    printf("Display in order..\n");
                    display(head);
                }
                break;
            }
            default: exit(0);
        }
    }
    return 0;
}

I am using Geany text editor and am on Linux Mint. I got a problem one where in the compiler just prints the last character I entered infinitely when I hit the display function. Any help will be very helpful! Thanks!

Answer 1

Your display function is wrong. The loop condition never evaluates to false:

while(&(*head)->lokid!=NULL && &(*head)->hikid!=NULL)

This is not what you want. None of &(*head)->lokid or &(*head)->hikid will ever evaluate to NULL. If head is not NULL, then &(*head)->lokid is just the same address as *head plus the offset of lokid in a struct tstree. Note that your loop doesn't even have an update statement that could possibly make the condition false, and it doesn't have any break - it's doomed.

In fact, you don't even need a loop at all. To print it in order, this is all you need:

void display(node *head) {
    if (head) {
        display(head->lokid);
        printf("%c ", head->letter);
        display(head->hikid);
    }
}

Note that there's no purpose in passing a node ** (I changed that to a node *), and the return value should be void.

UPDATE

Your insert() function is correct, but you use the wrong variable in main. This assignment in the recursion base from insert() is causing unintended behaviour:

temp = *head = malloc(sizeof(node));

Notice that every time you hit the base case, you assign a new node to *head and temp, thus losing reference to whatever was stored in temp before. Then you call display(temp). Yes, you build the trie, but you are printing it starting in the last inserted node - not what you want.

Instead, you should call display with the global variable head, which is the correct root of your trie:

display(head);

The same happens when you call insert. You do not want to insert a new letter starting on the last added node, you want to add it starting it on the root. main() should have this instead:

insert(num, &head);

And while we're at it, note that temp is completely unnecessary. You don't need it. insert manipulates the global head by reference, temp is of no use here (and in fact it introduced a bug).

Changing these 2 lines in main is enough, tested it here, and it's working like a charm.