How to Implement Trie in C#: Simple Guide with Example

To implement a Trie in C#, create a TrieNode class with a dictionary for children and a boolean to mark word end. Then build a Trie class with methods to insert and search words by traversing nodes.

Syntax

A TrieNode holds child nodes in a dictionary and a flag to mark if it ends a word. The Trie class manages the root node and provides Insert and Search methods to add and find words.

• Dictionary<char, TrieNode>: stores children nodes for each character.
• bool IsEndOfWord: marks if the node completes a valid word.
• Insert(string word): adds a word to the trie.
• Search(string word): checks if a word exists in the trie.

csharp

public class TrieNode
{
    public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
    public bool IsEndOfWord = false;
}

public class Trie
{
    private readonly TrieNode root = new TrieNode();

    public void Insert(string word)
    {
        var node = root;
        foreach (var ch in word)
        {
            if (!node.Children.ContainsKey(ch))
                node.Children[ch] = new TrieNode();
            node = node.Children[ch];
        }
        node.IsEndOfWord = true;
    }

    public bool Search(string word)
    {
        var node = root;
        foreach (var ch in word)
        {
            if (!node.Children.ContainsKey(ch))
                return false;
            node = node.Children[ch];
        }
        return node.IsEndOfWord;
    }
}

Example

This example shows how to create a trie, insert words, and search for them. It prints true for words found and false for words not inserted.

csharp

using System;
using System.Collections.Generic;

public class TrieNode
{
    public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
    public bool IsEndOfWord = false;
}

public class Trie
{
    private readonly TrieNode root = new TrieNode();

    public void Insert(string word)
    {
        var node = root;
        foreach (var ch in word)
        {
            if (!node.Children.ContainsKey(ch))
                node.Children[ch] = new TrieNode();
            node = node.Children[ch];
        }
        node.IsEndOfWord = true;
    }

    public bool Search(string word)
    {
        var node = root;
        foreach (var ch in word)
        {
            if (!node.Children.ContainsKey(ch))
                return false;
            node = node.Children[ch];
        }
        return node.IsEndOfWord;
    }
}

class Program
{
    static void Main()
    {
        var trie = new Trie();
        trie.Insert("apple");
        trie.Insert("app");
        Console.WriteLine(trie.Search("apple"));  // true
        Console.WriteLine(trie.Search("app"));    // true
        Console.WriteLine(trie.Search("apples")); // false
        Console.WriteLine(trie.Search("banana")); // false
    }
}

Output

True
True
False
False

Common Pitfalls

Common mistakes when implementing a trie include:

• Not marking the end of a word, causing Search to return false even if prefix exists.
• Using a list instead of a dictionary for children, which slows down lookups.
• Not handling empty strings or null inputs.

Always ensure IsEndOfWord is set correctly and use a dictionary for fast character lookup.

csharp

/* Wrong: Missing IsEndOfWord mark */
public void InsertWrong(string word)
{
    var node = root;
    foreach (var ch in word)
    {
        if (!node.Children.ContainsKey(ch))
            node.Children[ch] = new TrieNode();
        node = node.Children[ch];
    }
    // Forgot: node.IsEndOfWord = true;
}

/* Right: Mark end of word */
public void InsertRight(string word)
{
    var node = root;
    foreach (var ch in word)
    {
        if (!node.Children.ContainsKey(ch))
            node.Children[ch] = new TrieNode();
        node = node.Children[ch];
    }
    node.IsEndOfWord = true;
}

Quick Reference

• TrieNode: Holds children and end-of-word flag.
• Insert: Add characters, create nodes if missing, mark end.
• Search: Traverse nodes, return true if end-of-word reached.
• Use Dictionary<char, TrieNode> for fast child lookup.
• Always mark IsEndOfWord to distinguish words from prefixes.

Key Takeaways

Use a dictionary in TrieNode to store children for fast character lookup.

Always mark the end of a word with a boolean flag to distinguish full words from prefixes.

Insert words by creating nodes for each character if missing and mark the last node.

Search by traversing nodes for each character and check the end-of-word flag.

Avoid common mistakes like forgetting to mark the end of a word or using inefficient data structures.