Is this a valid implementation of trie Data structure?

Question

i am trying to learn Trie Data Structure and just implemented it without giving much attention to the code standards , its a raw implementation , can you guys help me to understand whether this implementation make some good progress?

Thanks

public class TrieNode
{
    public string Word { get; set; }

    public IList<TrieNode> Childs { get; set; }


}  

public class TheNobalTrie
{


   public TheNobalTrie()
   {
       RootNode = new TrieNode
                      {
                          Word = string.Empty,
                          Childs = new List<TrieNode>()

                      };

   }

   public bool AddWord(string word)
   {
       TrieNode firstNode = null;
       word = word.ToLower();
       int levelDepth = 0;
       while (true)
       {

           var tempWord = word[levelDepth];
           firstNode = RootNode.Childs.FirstOrDefault(x => x.Word[levelDepth].Equals(tempWord));

           if(firstNode==null)
           {
               RootNode.Childs.Add(AddNode(word, tempWord,0));
               return true;
           }
           var immidiateParentNode = firstNode;


           while (firstNode != null)
           {

               levelDepth++;

               //if below condition is true , it means word is being repeated so don't add it again.
               if (levelDepth == word.Length)
                   return false;

               tempWord = word[levelDepth];
               immidiateParentNode = firstNode;
               firstNode = firstNode.Childs.FirstOrDefault(x => x.Word[0].Equals(tempWord));

           }


           immidiateParentNode.Childs.Add(AddNode(word, tempWord,levelDepth));
           return true;
       }


   }

   public IList<string> GetMatchingWords(string word)
   {
       var list = new List<string>();
       word = word.ToLower();
       int levelDepth = 0;
       if (string.IsNullOrEmpty(word))
           return list;

       var tempWord = word[0];
       var firstNode = RootNode.Childs.FirstOrDefault(x => x.Word[0].Equals(tempWord));

       if (firstNode == null)
       {
           return list;
       }


       var nodePath = new Queue<TrieNode>();

       var sb = new StringBuilder();

       while (firstNode != null)
       {
          levelDepth++;

           if (levelDepth == word.Length)
           {
               break;
           }

           tempWord = word[levelDepth];
           firstNode = firstNode.Childs.FirstOrDefault(x => x.Word[0].Equals(tempWord));

       }

       if (firstNode != null)
           nodePath.Enqueue(firstNode);

      while (nodePath.Any())
       {
           var tempNode = nodePath.Dequeue();


           PopulateWords(tempNode, sb, ref list);

       }

      var tempList= list.Select(x => word + x).ToList();


      return tempList;
   }

   private void PopulateWords(TrieNode node,
        StringBuilder sb, ref List<string> list)
   {

       if (node.Childs.Any())
       {
           foreach (var temp in node.Childs)
           { 

               if (temp.Childs.Any())
               {
                   var tempBuilder = new StringBuilder();
                   tempBuilder.Append(sb);
                   tempBuilder.Append(temp.Word);
                   PopulateWords(temp, tempBuilder, ref list);


               }
               else
               {

                   sb.Append(temp.Word);
                   list.Add(sb.ToString());


               }

           }
       }
       else
       {

           list.Add(sb.ToString());

       }


   }

   private TrieNode AddNode(string word, char tempWord, int levelDepth)
   {
       var node = new TrieNode
                      {
                          Word = tempWord.ToString(),
                          Childs = new List<TrieNode>()
                      };
       var tempNode = node;
       for (int j = levelDepth+1; j < word.Length; j++)
       {
           var t = new TrieNode
                       {
                           Word = word[j].ToString(),
                           Childs = new List<TrieNode>()
                       };

           tempNode.Childs.Add(t);
           tempNode = t;
       }

       return node;
   }


   public TrieNode RootNode
       {
           get; private set;
       }

}

Answer 1

It looks like valid implementation, but it could be simplified. Also there are some naming issues: tempWord in AddWord method is actually a char and not a string. TrieNode.Word carries a single char but is declared as string.

You have a lot of trie management code inside TheNobalTrie class while it would be more readable to have the logic in TrieNode class: each node would be responsible for making decisions on its own level, delegating further decisions to its children. Also there is a common trie optimization that groups several chars in one node, e.g. if you have only dine and dinner words you would have 3 nodes: din with children (din)e and (din)ner