title: "Simple" Trie Implementation
body: <p>I need to implement a <a href="http://en.wikipedia.org/wiki/Trie" rel="noreferrer">Trie</a> (in Java) for a college project. The Trie should be able to add and remove Strings (for phase 1).</p>
  
  <p>I have spent several hours each day (for the last few days) trying to figure out how to do this and FAILED miserably each time.</p>
  
  <p>I require some help, the examples on the internet and my textbook (Data Structures and Algorithms in Java By Adam Drozdek) are not helping.</p>
  
  <h1>Information</h1>
  
  <ol>
  <li><p>Node classes I am working with:</p>
  
  <pre><code>class Node {
      public boolean isLeaf;
  }
  
  class internalNode extends Node {
      public String letters;  //letter[0] = '$' always.
      //See image -&gt; if letter[1] = 'A' then children[1] refers to child node "AMMO"
      //See image -&gt; if letter[2] = 'B' then children[2] refers to internal node "#EU"
      public TrieNode[] children = new TrieNode[2];
  
      public TrieInternalNode(char ch)
      {
          letters = "#" + String.valueOf(ch);//letter[0] = '$' always.
          isLeaf = false;
      }
  }
  
  class leafNode extends Node
  {
      public String word;
      public TrieLeafNode(String word)
      {
          this.word = new String(word);
          isLeaf = true;
      }
  }
  </code></pre></li>
  <li><p>And here is the pseudo code for insert that I need to follow: (warning it is very vague)</p>
  
  <pre><code>trieInsert(String K)
  {
      i = 0;
      p = the root;
      while (not inserted)
      {
          if the end of word k is reached
              set the end-of-word marker in p to true;
          else if (p.ptrs[K[i]] == 0)
              create a leaf containing K and put its address in p.ptrs[K[i]];
          else if reference p.ptrs[K[i]] refers to a leaf
          {
              K_L = key in leaf p.ptrs[K[i]]
              do
              {
                  create a nonleaf and put its address in p.ptrs[K[i]];
                  p = the new nonleaf;
              } while (K[i] == K_L[i++]);
          }
          create a leaf containing K and put its address in p.ptrs[K[--i]];
          if the end of word k is reached
              set the end-of-word marker in p to true;
          else
              create a leaf containing K_L and put its address in p.ptrs[K_L[i]];
          else
              p = p.ptrs[K[i++]];
      }
  }
  </code></pre></li>
  <li><p>I need to implement the following methods.</p>
  
  <pre><code>public boolean add(String word){...}//adds word to trie structure should return true if successful and false otherwise
  
  public boolean remove(String word){...}//removes word from trie structure should return true if successful and false otherwise
  </code></pre></li>
  <li><p>I cant find pseudo code for remove, but if insert does not work delete wont help me.</p></li>
  <li><p>Here is a image of how the Trie that I need to implement should look like.</p></li>
  </ol>
  
  <p><img src="https://i.stack.imgur.com/n4ZPM.jpg" alt="enter image description here"> </p>
  
  <ol start="6">
  <li><p>I am aware that the Trie will still be inefficient if implemented like this, but at the moment I need not worry about this.</p></li>
  <li><p>The book provides an implementation that is similar to what I need to do but doesn't use the end of word char ('$') and only stores the words without their prefixes in the child nodes <code>http://mathcs.duq.edu/drozdek/DSinJava/SpellCheck.java</code></p></li>
  </ol>
  
  <h1>Constraints</h1>
  
  <ol>
  <li>I need to implement the trie in JAVA.</li>
  <li>I may not import or use any of Java's built-in data structures. (ie. no Map, HashMap, ArrayList etc)</li>
  <li>I may use Arrays, Java primitive Types and Java Strings.</li>
  <li>The Trie must use a <code>$</code> (dollar) symbol to indicate a end-of-word. (see the image below )</li>
  </ol>
  
  <p><img src="https://i.stack.imgur.com/EtSj9.jpg" alt="enter image description here"></p>
  
  <ol start="5">
  <li>I may asume that now word containing the <code>$</code>symbol will be inserted.</li>
  <li>I need to implement the Trie it in the same style as the book does.</li>
  <li>Case of words doesn't matter ie. all words will be considered to be lowercase</li>
  <li>The Trie should only store the end-of-word character and the characters applicable to a word and not the entire alphabet(like some implementations).</li>
  </ol>
  
  <p>I do not expect anyone to do the implementation for me(unless they have one lying around :P) I just really need help.</p>