title: AutoComplete using a Trie in Java
body: <p>I am working on this assignment which implements Autocomplete and dictionary. I have sucessfully implemented spellcheck and the addWord() and isWord() functions.
  But I am just not able to implement the function which predicts words for AutoCompletions.</p>
  
  <pre><code>package spelling;
  
  import java.util.List;
  import java.util.Queue;
  import java.util.Set;
  import java.util.Collection;
  import java.util.Collections;
  import java.util.HashMap;
  import java.util.LinkedList;
  
  /** 
   * An trie data structure that implements the Dictionary and the AutoComplete ADT
   * @author You
   *
   */
  public class AutoCompleteDictionaryTrie implements  Dictionary, AutoComplete {
  private TrieNode root;
  private int size;
  
  
  public AutoCompleteDictionaryTrie()
  {
      root = new TrieNode();
      size=0;
  }
  
  
  /** Insert a word into the trie.
   * For the basic part of the assignment (part 2), you should ignore the word's case.
   * That is, you should convert the string to all lower case as you insert it. */
  public boolean addWord(String word)
  {
      //TODO: Implement this method.
      String Word=word.toLowerCase();
      if(isWord(Word))
          return false;
      HashMap&lt;Character, TrieNode&gt; children=root.children;
      for(int i=0; i&lt;Word.length(); i++){
          char c = Word.charAt(i);
          TrieNode t;
          if(children.containsKey(c)){
                  t = children.get(c);
          }else{
              t = new TrieNode(""+(c));
              children.put(c, t);
          }
  
          children = t.children;
          if(i==Word.length()-1)
          {
              t.isWord = true; 
              size++;
          }
      }
      return true;
  }
  
  /** 
   * Return the number of words in the dictionary.  This is NOT necessarily the same
   * as the number of TrieNodes in the trie.
   */
  public int size()
  {
      //TODO: Implement this method
      return size;
  }
  
  
  /** Returns whether the string is a word in the trie */
  @Override
  public boolean isWord(String s) 
  {
      // TODO: Implement this method
      TrieNode t = searchNode(s.toLowerCase());
  
      if(t != null &amp;&amp; t.isWord) 
          return true;
      else
          return false;
  }
  public TrieNode searchNode(String str){
      HashMap&lt;Character, TrieNode&gt; children = root.children; 
      TrieNode t = null;
      for(int i=0; i&lt;str.length(); i++){
          char c = str.charAt(i);
          if(children.containsKey(c)){
              t = children.get(c);
              children = t.children;
          }else{
              return null;
          }
      }
  
      return t;
  }
  
  /** 
   *  * Returns up to the n "best" predictions, including the word itself,
   * in terms of length
   * If this string is not in the trie, it returns null.
   * @param text The text to use at the word stem
   * @param n The maximum number of predictions desired.
   * @return A list containing the up to n best predictions
   */@Override
   public List&lt;String&gt; predictCompletions(String prefix, int numCompletions) 
   {
       // TODO: Implement this method
       // This method should implement the following algorithm:
       // 1. Find the stem in the trie.  If the stem does not appear in the trie, return an
       //    empty list
       // 2. Once the stem is found, perform a breadth first search to generate completions
       //    using the following algorithm:
       //    Create a queue (LinkedList) and add the node that completes the stem to the back
       //       of the list.
       //    Create a list of completions to return (initially empty)
       //    While the queue is not empty and you don't have enough completions:
       //       remove the first Node from the queue
       //       If it is a word, add it to the completions list
       //       Add all of its child nodes to the back of the queue
       // Return the list of completions
       List&lt;String&gt; completions=null;
       int counter=0;
       if (prefix==null){
           return Collections.emptyList();
       }
  
       prefix=prefix.toLowerCase();
       if(isWord(prefix))
           completions.add(prefix);
       LinkedList nodes = new LinkedList();
  
       TrieNode curr=searchNode(prefix);
       nodes.addLast(curr);
       while(!nodes.isEmpty() &amp;&amp; counter!=numCompletions)
       {
           if((nodes.removeFirst()).isWord)
           completions.add(curr.getText());
           TrieNode next = null;
           for (Character c : curr.getValidNextCharacters()) {
                  next = curr.getChild(c);
           }
       }
  
  
       return Collections.emptyList();
  
   }
   public void checkNull(String word){
      if (word==null)
          throw new NullPointerException("Null word passed");
   }
  // For debugging
  public void printTree()
  {
      printNode(root);
  }
  
  /** Do a pre-order traversal from this node down */
  public void printNode(TrieNode curr)
  {
      if (curr == null) 
          return;
  
      System.out.println(curr.getText());
  
      TrieNode next = null;
      for (Character c : curr.getValidNextCharacters()) {
          next = curr.getChild(c);
          printNode(next);
      }
  }
  
  
  
  }
  </code></pre>
  
  <p>And this is the code of the TrieNode class:</p>
  
  <pre><code>package spelling;
  
  import java.util.HashMap;
  import java.util.Set;
  
  /** 
  * Represents a node in a Trie
  * @author UC San Diego Intermediate Programming MOOC Team
  *
   */
  class TrieNode {
  HashMap&lt;Character, TrieNode&gt; children; 
  private String text;  // Maybe omit for space
  boolean isWord;
  
  /** Create a new TrieNode */
  public TrieNode()
  {
      children = new HashMap&lt;Character, TrieNode&gt;();
      text = "";
      isWord = false;
  }
  
  /** Create a new TrieNode given a text String to store in it */
  public TrieNode(String text)
  {
      this();
      this.text = text;
  }
  
  /** Return the TrieNode that is the child when you follow the 
   * link from the given Character 
   * @param c The next character in the key
   * @return The TrieNode that character links to, or null if that link
   *   is not in the trie.
   */
  public TrieNode getChild(Character c)
  {
      return children.get(c);
  }
  
  /** Inserts this character at this node.
   * Returns the newly created node, if c wasn't already
   * in the trie.  If it was, it does not modify the trie
   * and returns null.
   * @param c The character that will link to the new node
   * @return The newly created TrieNode, or null if the node is already 
   *     in the trie.
   */
  public TrieNode insert(Character c)
  {
      if (children.containsKey(c)) {
          return null;
      }
  
      TrieNode next = new TrieNode(text + c.toString());
      children.put(c, next);
      return next;
  }
  
  /** Return the text string at this node */
  public String getText()
  {
      return text;
  }
  
  /** Set whether or not this node ends a word in the trie. */
  public void setEndsWord(boolean b)
  {
      isWord = b;
  }
  
  /** Return whether or not this node ends a word in the trie. */
  public boolean endsWord()
  {
      return isWord;
  }
  
  /** Return the set of characters that have links from this node */
  public Set&lt;Character&gt; getValidNextCharacters()
  {
      return children.keySet();
  }
  
  }
  </code></pre>
  
  <p>Even though the algorithm is there I am not able to implement it. Any kind of help would be greatly appreciated.</p>