title: tries data structure implementation......... Application - Dictionary
body: <p>Wanted to write a program to implement a dictionary of words using <strong>Tries Data Structure</strong>.</p>
  
  <p>Please tell me the structure for the implementation so that I could start the program, as i haven't got any article on internet, for Tries Implementation..</p>
  
  <p>The confusion is, that when we search through the word, and we get through the word at the leaf node, only then is the meaning of the word would be stored.. But all the nodes in Tries data structure will be of waste. i.e. storing a variable of meaning in every internal node......</p>
  
  <p>So, the basic idea, is with a help of small example as how to store dictionary, please let me know the structure for Tries Data Structure.. </p>
  
  <p>And please C program Implementation..</p>
  
  <p>Thanks..</p>
  
  <p>Compressed Tries.. This is giving me the correct Compressed Trie, as expected,,,, but there are some issues with it.... And wanted to discuss that....</p>
  
  <p>1)   I Build a simple trie first, and then compressed it using a function trie_compress(), Now when i want to add any word into it, it would want a changed trie_add(), also changed trie_lookup(), ok i will do this on my own, just wanted to know, is my approach correct or there could be some better way..</p>
  
  <p>2)   In trie_new(), I have used        t->substr = (char*)malloc(10);,,,,,, This doesn't look efficient, as memory should be allocated, as in when required. Can we improve upon this.</p>
  
  <pre><code>typedef struct trie
  {
     int on;
     char *substr;
     struct trie *first_child;
     struct trie *next_sibling;
  }trie;
  
  trie* trie_new()
  {
     trie *t = (trie*)malloc(sizeof(trie));
     t-&gt;substr = (char*)malloc(10);
     t-&gt;on = 0;
     t-&gt;substr[0] = '\0';
     t-&gt;first_child = NULL;
     t-&gt;next_sibling = NULL;
  
     return t;
  }
  
  trie* trie_at_level(trie *t, char c)
  {
     while(t != NULL)
     {
        if(t-&gt;substr[0] == c)
        {
           return t;
        }
        t = t-&gt;next_sibling;
     }
     return NULL;
  }
  
  void trie_add(trie *t, const char *str)
  {
     const int n = strlen(str);
     int i;
  
     for(i=0; i&lt;n; i++)
     {
        const char c = str[i];
        trie* parent = t;
  
        t = t-&gt;first_child;
        t = trie_at_level(t,c);
        if(t == NULL)
        {
           t = trie_new();
           t-&gt;substr[0] = c;
           t-&gt;substr[1] = '\0';
           t-&gt;next_sibling = parent-&gt;first_child;
           parent-&gt;first_child = t;
        }
     }
     t-&gt;on = 1;
  }
  
  int trie_lookup(trie *t, const char *str)
  {
     const int n = strlen(str);
     int i;
  
     for(i=0; i&lt;n; i++)
     {
        const char c = str[i];
        t = t-&gt;first_child;
        t = trie_at_level(t,c);
        if(t == NULL)
           return 0;
     }
     return t-&gt;on;
  }
  
  void trie_compress(trie *t)
  {
     trie* parent = t;
     t = t-&gt;first_child;
  
     if(t-&gt;first_child != NULL)
        trie_compress(t);
  
     if(t-&gt;next_sibling == NULL)
     {
        parent-&gt;substr = strcat(parent-&gt;substr,t-&gt;substr);
        parent-&gt;first_child = t-&gt;first_child;
        parent-&gt;on = t-&gt;first_child-&gt;on;
        free(t);
  
        return;
     }
     else
        trie_compress(t-&gt;next_sibling);
  }
  </code></pre>