Gist 2 from the article Autocomplete functionality using prefix trees

autocomplete prefix trees gist 2

  /// <summary>
  /// get the autocomplete matches given the input
  /// </summary>
  /// <param name="query">the input</param>
  /// <returns>the list of autocomplete matches</returns>
  public List<string> GetMatches(string query)
  {
      StringBuilder sbPrevious = new StringBuilder();
      char[] chars = query.ToCharArray();
      Node currentNode = _root;
      Node child = null;
      for (int counter = 0; counter < chars.Length; counter++)
      {
          //form the sequence before the current char
          if(counter < chars.Length - 1)
              sbPrevious.Append(chars[counter]);

          child = currentNode.GetChild(chars[counter]);
          if (child == null)
              break;
          currentNode = child;
      }

      //clear the subsequent string storage
      subsequentStrings.Clear();

      GenerateSubsequentStrings(currentNode, sbPrevious.ToString());

      return subsequentStrings;
  }

  /// <summary>
  /// given a node and the current string generate the autocomplete matches recursively
  /// </summary>
  /// <param name="node">the current node</param>
  /// <param name="subsequentString">the current sequence</param>
  private void GenerateSubsequentStrings( Node node,
                                                  string subsequentString)
  {
      //if there are no more nodes stop the recursion
      if(node == null)
          return;

      //add the current char to the current sequence
      subsequentString = subsequentString + node.Char;

      //if a word ends here add the current sequence to the autocomplete list
      if(node.AWordEndsHere)
          subsequentStrings.Add(subsequentString);

      //foreach child call the method recursively
      foreach (var subnode in node.Subtree)
          GenerateSubsequentStrings(subnode, subsequentString);
  }