Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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;
       }

}

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.