# Is this a valid implementation of trie Data structure?

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>()

};

}

{
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)
{
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));

}

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

}

}
}
else
{

}

}

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

return node;
}

public TrieNode RootNode
{
get; private set;
}


}

-

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