title: algorithm to print trie alphabetically
body: <p>I've been busy trying to code a trie ordered tree data structure in C. My program reads in words in a sentence one at a time from a .txt, then it stores each word in a trie without duplicates. It then grabs all other words in that sentence and stores them in a subtrie of the word that was stored. For example if we had the following sentence: "contribute to open source. " My code does the following... </p>
  
  <pre><code>            root
    ab'c'defghijklmn'o'pqr's''t'uvwxyz
      'o'           'p'   'o''o'-subtrie-&gt; "contribute", "open", "source"
      'n'           'e'   'u'
      't'           'n'   'r'
      'r'                 'c'-subtrie-&gt;"contribute", "to", "open", 
      'i'                     
      'b'
      'u'
      't'
      'e'-subtrie-&gt; "to", "open", "source" 
  </code></pre>
  
  <p>I have successfully been able to insert words into the trie and also the subtries. I have thoroughly tested this so I am pretty confident everything works the way it was intended to.  However, i cant seem to figure out the algorithem to print the trie and subtrie alphabetically. </p>
  
  <p>Here's the struct i am using </p>
  
  <pre><code>typedef struct TrieNode
  {
       // number of times this string occurs in the corpus
   int count;
  
  // 26 TrieNode pointers, one for each letter of the alphabet
  struct TrieNode *children[26];
  
  // the co-occurrence subtrie for this string
  struct TrieNode *subtrie;
  } TrieNode;
  </code></pre>
  
  <p>here is the function i wrote to insert tries. The parameters are the root of the trie, a char array of the word i want to insert, size of the word i am inserting, z = -1 initially. </p>
  
  <pre><code>TrieNode *trieInsert(TrieNode *root, char *wordArray, int sizeOfWord, int z){
  
      z++;
      int x1, j, index; 
      char c1 = wordArray[z];     
  
      //INSERT char second level 
      // do alphaNum conversions and check uper or lower case for lev1Char
      x1 = char2Num(c1);
          if(x1 &gt;26 ){
          printf("ERRRRRRRRRRRRRRRRRRrr:line475");
      return root;
      }
  
      //base case
      if( sizeOfWord == z ) 
      return root; 
  
      //check to see if we already inserted this 
      if( root-&gt;children[x1] == NULL ){ 
  
      //we insert second letter 
      root-&gt;children[x1] = malloc(sizeof(struct TrieNode) );
              root-&gt;children[x1]-&gt;subtrie = NULL;
      root-&gt;children[x1]-&gt;count = 0;  
      //set children of newly malloced to null 
      for(j = 0; j &lt; 27; j++)
          root-&gt;children[x1]-&gt;children[j] = NULL;
  
      }
  
      //increment word count on last char of word 
      if((sizeOfWord - 1) == z) 
      root-&gt;children[x1]-&gt;count++;    
  
      return trieInsert(root-&gt;children[x1], wordArray, sizeOfWord, z);
  
  }
  </code></pre>
  
  <p>Here is the code i cant figure out. It was to print the trie alphabetically, however, it's output is incorrect. </p>
  
  <pre><code>void printTrieAlefBet( TrieNode *root ){
  
      int i; 
  
      if( root-&gt;subtrie != NULL){
          printf(" (%d)", root-&gt;count);
          return;  
      }
  
  
      for( i = 0; i &lt; 27; i++)
          if( root-&gt;children[i] != NULL){
              printTrieAlefBet(root-&gt;children[i]);
              printf("%c", num2Char(i, 0) );
          }
  
  
  }
  </code></pre>
  
  <p>Any thoughts would be greatly appreciated! </p>