// Trie (Prefix Tree)

core idea

A trie is a tree where edges spell characters and root-to-node paths spell prefixes. Insert "car" and "care" and they share the nodes for c, a, r — only e is new. Every node is a tiny dictionary of “what character can I go to next,” so the cost of a lookup is the length of the string, never the number of words stored. That’s the whole trade you’re making: pay per character inserted, get prefix search for free.

The one real design decision is how a node stores its children:

when to reach for it

• The problem statement says prefix, starts with, or ships a dictionary of words you’ll query repeatedly.
• You need autocomplete-style lookups: “what words begin with this prefix?”
• A wildcard character (. meaning “any letter”) appears in the search — a trie turns that into a small DFS over children instead of testing every stored word.
• Many words share long prefixes and you’d be repeating work with a plain HashSet<string>.

universal templates

Dictionary-based node — the default, works for any alphabet:

public class TrieNode
{
    public Dictionary<char, TrieNode> Children { get; } = [];   // sparse: pay only for chars used
    public bool IsWord;                                          // true at nodes that end a word
}

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

    public void Insert(string word)
    {
        var node = _root;
        foreach (char c in word)
        {
            if (!node.Children.TryGetValue(c, out var next))
                node.Children[c] = next = new TrieNode();        // extend the tree on the first miss
            node = next;
        }
        node.IsWord = true;                                       // mark the path we just walked
    }

    public bool Search(string word)
    {
        var node = _root;
        foreach (char c in word)
        {
            if (!node.Children.TryGetValue(c, out var next)) return false;  // path breaks → not stored
            node = next;
        }
        return node.IsWord;                                       // path exists, but is it a full word?
    }
}

Array-based node — same shape, a-z only, no hashing:

public class TrieNode
{
    public TrieNode?[] Children { get; } = new TrieNode?[26];    // index c - 'a' directly
    public bool IsWord;
}

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

    public void Insert(string word)
    {
        var node = _root;
        foreach (char c in word)
            node = node.Children[c - 'a'] ??= new TrieNode();    // create-if-missing in one line

        node.IsWord = true;
    }

    public bool Search(string word)
    {
        var node = _root;
        foreach (char c in word)
        {
            node = node.Children[c - 'a'];
            if (node is null) return false;
        }
        return node.IsWord;
    }
}

Every problem below is Insert plus a walk over Children — search, wildcard search, and grid backtracking are all the same walk with a different stopping rule.

problems

Three problems, one structure: build it, search it with a wildcard, then run a grid search through it.

1. 01Implement TriemediumLC #208

   Insert, search, startsWith — nodes with child maps and an end-of-word flag.

2. 02Design Add and Search WordsmediumLC #211

   Trie search with '.' wildcards — DFS over all children.

3. 03Word Search IIhardLC #212stretch

   Trie + grid backtracking. Prerequisite: Word Search (backtracking).