title: Trie implementation - Inserting elements into a trie
body: <p>I am developing a <code>Trie</code> data-structure where each node represents a word. So words <code>st</code>, <code>stack</code>, <code>stackoverflow</code> and <code>overflow</code> will be arranged as </p>
  
  <pre><code>root
  --st
  ---stack
  -----stackoverflow
  --overflow
  </code></pre>
  
  <p>My Trie uses a <code>HashTable</code> internally so all node lookup will take constant time. Following is the algorithm I came up to insert an item into the trie.</p>
  
  <ol>
  <li>Check item existence in the trie. If exist, return, else goto step2.</li>
  <li>Iterate each character in the <code>key</code> and check for the existence of the word. Do this until we get a node where the new value can be added as child. If no node found, it will be added under root node.</li>
  <li>After insertion, rearrange the siblings of the node under which the new node was inserted. This will walk through all the siblings and compare against the newly inserted node. If any of the node starts with same characters that new node have, it will be moved from there and added as child of new node.</li>
  </ol>
  
  <p>I am not sure that this is the correct way of implementing a trie. Any suggestions or improvements are welcome.</p>
  
  <p>Language used : C++</p>