Trie only inserting first letter of a word, not the whole word

Question

I am currently working a program where I am inserting words into a trie. Currently my insert function only adds in the first letter of the word and then stops. From everything I have looked up, my code looks correct, so I don't understand what the issue is.

I have tried moving the temp-> wordEnd = true to the outside of the for loop and within different locations in the function. For I believe this is the problem, due to everything else in my insert function looking correct.

Here is my insert function:

bool Trie::insert(string word)
{
    TrieNode *temp = root;
    temp->prefixAmount++;

    for (int i = 0; i < word.length(); ++i)
    {
        int currentLetter = (int)word[i] - (int)'a';
        if (temp->child[currentLetter] == NULL)
        {
            temp->child[currentLetter] = new TrieNode();
            temp->child[currentLetter]->prefixAmount++;
            temp = temp->child[currentLetter];
        }
        temp->wordEnd = true;
        return true;
    }
}

Also to help everyone follow my code a little bit better Here is my TrieNode struct:

  struct TrieNode
   {
     int prefixAmount;
     struct TrieNode *child[ALPHA_SIZE];
    bool wordEnd;

   };

And here is my Trie constructor:

   Trie::Trie()
    {
      root = new TrieNode();
      root->wordEnd = false;
     root->prefixAmount = 0;

     }

The expected results are suppose to be that the whole word get inserted. What actually happens is that only the first letter of the word gets added.

Answer 1

I've reformatted the code for you, and now you should hopefully see the main issue.

You are returning at the end of the block within the for loop. This will mean that it runs the first iteration of the for loop and just return without considering the rest of the letters.

An easy fix would be to put the return outside the for loop but there is another issue that you dont properly update the Trie if the current letter is already in it. Your NULL check is correct, but you should only new up the TrieNode on NULL but you also want to run all subsequent lines even if its not NULL. Fixed code will look like:

bool Trie::insert(string word)
{
    TrieNode *temp = root;
    temp->prefixAmount++;

    for (int i = 0; i < word.length(); ++i)
    {
        int currentLetter = (int)word[i] - (int)'a';
        if (temp->child[currentLetter] == NULL)
        {
            temp->child[currentLetter] = new TrieNode();
        }
        temp->child[currentLetter]->prefixAmount++;
        temp = temp->child[currentLetter];
    }
    temp->wordEnd = true;
    return true;
}

(Other minor issues in the code outside the scope of the question - prefer nullptr to NULL, why return a bool if its always true, if your string contains anything outside of a-z then you'll read outside the array bounds, prefer unique_ptr and make_unqiue to raw new/delete).