title: Ternary search tree with all suggestions autocomplete in C#
body: <p>I wonder is it possible to modify ternary search tree to check that word exists <strong>AND</strong> find all words that starts with that word ( or finish by that word ?) ?
  For example <code>do</code> => <code>dog</code> <code>dogs</code> etc.</p>
  
  <p>From this <a href="http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/" rel="nofollow">site</a> is a sample code. First load all words to ternary tree then we can use method to check if word exists.</p>
  
  <pre><code>public class TernaryTree
  {
      private Node m_root = null;
  
      private void Add(string s, int pos, ref Node node)
      {
          if (node == null) { node = new Node(s[pos], false); }
  
          if (s[pos] &lt; node.m_char) { Add(s, pos, ref node.m_left); }
          else if (s[pos] &gt; node.m_char) { Add(s, pos, ref node.m_right); }
          else
          {
              if (pos + 1 == s.Length) { node.m_wordEnd = true; }
              else { Add(s, pos + 1, ref node.m_center); }
          }
      }
  
      public void Add(string s)
      {
          if (s == null || s == "") throw new ArgumentException();
  
          Add(s, 0, ref m_root);
      }
  
      public bool Contains(string s)
      {
          if (s == null || s == "") throw new ArgumentException();
  
          int pos = 0;
          Node node = m_root;
          while (node != null)
          {
              int cmp = s[pos] - node.m_char;
              if (s[pos] &lt; node.m_char) { node = node.m_left; }
              else if (s[pos] &gt; node.m_char) { node = node.m_right; }
              else
              {
                  if (++pos == s.Length) return node.m_wordEnd;
                  node = node.m_center;
              }
          }
  
          return false;
      }
  }
  
  class Node
  {
      internal char m_char;
      internal Node m_left, m_center, m_right;
      internal bool m_wordEnd;
  
      public Node(char ch, bool wordEnd)
      {
          m_char = ch;
          m_wordEnd = wordEnd;
      }
  }
  </code></pre>
  
  <p>This make me loome large in my mind :(<br />
  Any way to get that words could be anything. However I am weak in algorithms with that level..<br />
  I hope that I don't duplicate any questions about this.
  Any suggestion I will appreciate for.</p>