title: How to calculate the number of nodes in a trie, given a set of words
body: <p>Wondering if there is a generic algorithm or technique for calculating how many nodes (and so, how many bytes) are in a trie.</p>
  
  <p>So say there is a trie that starts off like this:</p>
  
  <pre><code>   a        t
     p        h
  e  p        e  i
     l  s  r  i  s
     e     e  r
  
  ape
  apps
  apple
  the
  their
  there
  this
  </code></pre>
  
  <p>Then imagine that there is instead a large dictionary of thousands of words. Each word consists of a set of letters <code>L</code> from an alphabet <code>A</code>. So essentially we can generate <code>n</code> number of <code>L</code>'s (words), say 100,000, of various lengths. They will overlap in certain situations, so the number of bytes it takes up in the final trie won't just be 100,000 x (avg length) sort of thing. It will instead be some fraction of the total.</p>
  
  <p>I'm wondering how to calculate this. If you need to actually generate the data and then measure it, or if there is a mathematical technique for approximately modelling it quickly.</p>