title: Space efficient trie
body: <p>I'm trying to implement a space efficient trie in C. This is my struct:</p>
  
  <pre><code>struct node {
  char val; //character stored in node
  int key; //key value if this character is an end of word
  struct node* children[256];
  };
  </code></pre>
  
  <p>When I add a node, it's index is the unsigned char cast of the character. For example, if I want to add "c", then</p>
  
  <pre><code>children[(unsigned char)'c']
  </code></pre>
  
  <p>is the pointer to the newly added node. However, this implementation requires me to declare a node* array of 256 elements. What I want to do is:</p>
  
  <pre><code>struct node** children;
  </code></pre>
  
  <p>and then when adding a node, just malloc space for the node and have </p>
  
  <pre><code>children[(unsigned char)'c']
  </code></pre>
  
  <p>point to the new node. The issue is that if I don't malloc space for children first, then I obviously can't reference any index or else that's a big error. </p>
  
  <p>So my question is: how do I implement a trie such that it only stores the non-null pointers to its children?</p>