implementing a TRIE data structure

Question

Hii , i Was implementing a trie in C ... but i am getting an error in the insert_trie function .

I could not figure out why the root node is not getting updated . Please help me with this.

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

typedef struct
 {
  char value;
  int level;
  struct node *next;
  struct node *list;
 }node;

 node *trie = NULL;

 node *init_trie()
  {
   node *new = (node *)malloc(sizeof(node));
   if(trie == NULL)
    {
     new->value = '$';
     new->next = NULL;
     new->list = NULL;
     new->level = 0;
     trie = new;
     printf("\n Finished initializing the trie with the value %c",trie->value);
     return trie;
    }
    printf("\n Trie is already initialized");
    return trie;
  }  

 node *insert_trie(char *s)
  {
   node *nodepointer = trie;
   node *new = (node *)malloc(sizeof(node));
   node *save = NULL;
   int i=0;
   while(s[i]!=NULL)
    {
       nodepointer = nodepointer->list;
     while(nodepointer!=NULL)
      {
        if(s[i] == nodepointer->value)
         {
          printf("\n Found %c",nodepointer->value);
          nodepointer = nodepointer->list;
          i++;
         }
         save = nodepointer;
         nodepointer = nodepointer->next;
      }
      new->value = s[i];
      new->next = NULL;
      new->list = NULL;
      printf("\n Inserting %c",new->value);
      save->next = new;     
      i++;
    }

   return trie;
  } 


 int main()
  {

   int num;
   char *s = (char *)malloc(sizeof(char)*10);
   trie = init_trie();
   printf("\n Enter the number of words to enter into the trie "); 
   scanf("%d",&num);
   while(num>0)
   {
   scanf("%s",s);
   //printf("%s",s);
   trie = insert_trie(s);
   printf("\n Finished inserting the word %s into the trie \n",s);
   num --;
   } 
   return 0;
  } 

I get a segmentation fault due to the line nodepointer = nodepointer->list in insert_trie function ... Why ????

P.S : This is not homework.But i am trying to implement it. I just could not find the mistake .

Solution 1

"Implement a trie with insert, search, and startsWith methods. Note: You may assume that all inputs are consist of lowercase letters a-z."

I have written this very simple solution for the above question from LeetCode. It has passed all the 16 test cases from LeetCode. I hope this will help.

//node structure
struct TrieNode {
     char value;
     int count;
    struct TrieNode * children[27];
};


static int count =0;
/** Initialize your data structure here. */
//return root pointer
struct TrieNode* trieCreate() {
    struct TrieNode *pNode = NULL;

    pNode = (struct TrieNode *)malloc(sizeof(struct TrieNode));

    if (pNode)
    {
        pNode->value = '\0';
        pNode->count =0;

        memset(pNode->children, 0, sizeof(pNode->children));

    }
    return pNode;


}

/** Inserts a word into the trie. */
void insert(struct TrieNode* root, char* word) {

    struct TrieNode *pCrawl = root;
    count ++;
    //check if the word is not empty 
    if(word){
    int index=0, i =0;

    //check if the root is not empty
    if (root){

    while( word[i] != '\0'){
        index =  ( (int) (word[i]) - (int)'a');

        if(!pCrawl->children[index])
        {
            pCrawl->children[index] = trieCreate();
            pCrawl->children[index]->value = word[i];
        }

        pCrawl = pCrawl->children[index];
        i++;

    }

         //Count !=0 tell us that this is the last node;;
    pCrawl->count = count;

    }
}}



/** Returns if the word is in the trie. */
bool search(struct TrieNode * root, char* word) {

    struct TrieNode *pCrawl = root;
    bool flag = false;

    //check if word is NULL
    if(!word)
    return false;

    //if the trie is empty
    if(!root)
    {
        return false;
    }
    //if word is empty
    if (*word == '\0') {
        return true;
    }

    int i=0, index =0 ; 


    while (word[i] != '\0')
    {
     index = ((int) (word[i]) - (int)'a');

         //// if the node/character is not in Trie
        if(!pCrawl->children[index])
        {
            flag = false;
             break;
        }

        pCrawl = pCrawl->children[index];
        i++;
    }

          //count != 0 marks node as last / leaf node
          if(pCrawl->count != 0 && word[i] == '\0')
          {
              flag = true;
          }
        return flag;

}

/** Returns if there is any word in the trie 
    that starts with the given prefix. */
bool startsWith(struct TrieNode* root, char* prefix) {

    struct TrieNode * pCrawl = root;

    int i =0, index=0;
    bool flag = false;
    if(root){
    while(prefix[i] != '\0')
    {
         index = ((int) (prefix[i]) - (int)'a');

     if(pCrawl->children[index] == NULL){
     flag = false;
         return flag;
     }
     else 
     flag = true;

     pCrawl = pCrawl->children[index];
     i++;
    }

    }

    return flag;


}

/** Deallocates memory previously allocated for the TrieNode. */
void trieFree(struct TrieNode* root) {

    if(root){

        for(int i = 0; i <=26; i ++)
        {
            trieFree(root->children[i]);
        }
        free(root);

    }

}

// Your Trie object will be instantiated and called as such:
// struct TrieNode* node = trieCreate();
// insert(node, "somestring");
// search(node, "key");
// trieFree(node);

Solution 2

A trie holds one node per character and you're only performing one malloc per string. You should be calling malloc for every node. (Also, malloc.h is outdated. stdlib.h contains malloc since the ANSI C standard of 1989.)

Solution 3

node *insert_trie(char *s) 
  { 
   node *nodepointer = trie; 
   node *new = (node *)malloc(sizeof(node)); 
   node *save = NULL; 
   int i=0; 
   while(s[i]!=NULL) 
    { 
       nodepointer = nodepointer->list; 
     while(nodepointer!=NULL) 
      { 
        if(s[i] == nodepointer->value) 
         { 
          printf("\n Found %c",nodepointer->value); 
          nodepointer = nodepointer->list; // Advance pointer once OK
          i++; 
         } 
         save = nodepointer; 
         nodepointer = nodepointer->next; // Advance pointer without checking
      } 
      new->value = s[i]; 
      new->next = NULL; 
      new->list = NULL; 
      printf("\n Inserting %c",new->value); 
      save->next = new;      
      i++; 
    } 

   return trie; 
  } 

Within the if test you advance nodepointer to nodepointer->list. Once the if test completes you advance nodepointer to nodepointer->next without checking if nodepointer is NULL from the advancement which occured within the if block.