What is a trie (prefix tree)? Implement insert, exact search and prefix search in C#, and discuss when a trie is the right choice for something like autocomplete versus alternatives.

1. Node design choices

2. Compressed (radix) trie

Plain trie:   r ─ o ─ m ─ a ─ n ─ e*        Radix trie:   "roman" ─ "e"*
                          └─ u ─ s*                                   └ "us"*

Chains of single children are merged into one edge labelled with a string, which saves many nodes. Routers and some key-value stores use radix trees.

3. Ranking and limits

Real autocomplete needs the best suggestions, not all of them. Options:

• Store a small top-K list at each node (precomputed): O(L) query, more memory.
• Collect the subtree with DFS and keep a size-K heap by score.
• Cap results and depth to avoid huge responses for one-letter prefixes.

4. Normalisation

Decide how to treat case, accents and spaces before inserting: e.g. "Wagga Wagga" → "wagga wagga", strip diacritics with string.Normalize(NormalizationForm.FormD) and remove combining marks. Apply the same normalisation to queries.

5. Alternatives in practice

6. Try it yourself

1. Implement the trie in the code example and load 100,000 English words; measure memory with GC.GetTotalMemory.
2. Implement the sorted-array alternative and compare memory and prefix query speed.
3. Add a top-5 list per node and compare latency for one-letter prefixes.

public sealed class Trie
{
    private sealed class Node
    {
        public Dictionary<char, Node> Children { get; } = new();
        public bool IsWord { get; set; }
    }

    private readonly Node _root = new();

    public void Insert(string word)
    {
        var node = _root;
        foreach (var c in Normalise(word))
        {
            if (!node.Children.TryGetValue(c, out var next))
            {
                next = new Node();
                node.Children[c] = next;
            }
            node = next;
        }
        node.IsWord = true;
    }

    public bool Contains(string word) => Find(Normalise(word)) is { IsWord: true };

    public IEnumerable<string> StartsWith(string prefix, int limit = 10)
    {
        var normalised = Normalise(prefix);
        var start = Find(normalised);
        if (start is null) yield break;

        // Iterative DFS so deep words cannot overflow the call stack
        var stack = new Stack<(Node Node, string Text)>();
        stack.Push((start, normalised));
        int count = 0;
        while (count < limit && stack.TryPop(out var item))
        {
            if (item.Node.IsWord) { yield return item.Text; count++; }
            foreach (var (c, child) in item.Node.Children.OrderByDescending(kv => kv.Key))
                stack.Push((child, item.Text + c));   // push in reverse so output is alphabetical
        }
    }

    private Node? Find(string text)
    {
        var node = _root;
        foreach (var c in text)
        {
            if (!node.Children.TryGetValue(c, out var next)) return null;
            node = next;
        }
        return node;
    }

    private static string Normalise(string s) => s.Trim().ToLowerInvariant();
}

// Usage
var suburbs = new Trie();
foreach (var s in new[] { "Sydney", "Sydenham", "Sylvania", "Melbourne" }) suburbs.Insert(s);
Console.WriteLine(string.Join(", ", suburbs.StartsWith("syd")));   // sydenham, sydney
Console.WriteLine(suburbs.Contains("SYDNEY"));                       // True

// Compact alternative: sorted array + binary search for a prefix range
string[] sorted = names.Select(n => n.ToLowerInvariant()).Order(StringComparer.Ordinal).ToArray();

IEnumerable<string> PrefixSearch(string prefix)
{
    int i = Array.BinarySearch(sorted, prefix, StringComparer.Ordinal);
    if (i < 0) i = ~i;                                  // first position >= prefix
    for (; i < sorted.Length && sorted[i].StartsWith(prefix, StringComparison.Ordinal); i++)
        yield return sorted[i];
}