Separate trie words from prefixes

Clarify the observable contract

A trie represents shared prefixes with paths, but a path is not automatically a complete stored word. A terminal flag distinguishes car from its prefix ca. This implementation uses exact UTF-16 code units, permits an empty prefix and treats repeated insertion as idempotent. Inserting the empty word would mark the root terminal; no case folding, normalization or grapheme matching is implied.

Word membership and prefix membership are separate operations with separate expected answers. The root represents the empty prefix even in a trie that contains no words. A terminal bit records word completion independently of whether a node has children, so a word can also be the prefix of a longer word.

Walk through the verified program

Inserting car creates c,a,r; cart reuses that path and adds t. Cat shares c,a and adds another branch. Re-inserting car leaves its terminal flag true. The path for ca exists but its node is not terminal, while car is terminal. Finding an empty prefix returns the root, even though no empty word was inserted.

After car and cart are inserted, the r node is terminal and has a t child. Neither fact cancels the other. The shared c,a path branches at r and t for car and cat. Repeated car insertion changes no counts because this implementation stores membership rather than occurrence frequency.

using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;

var trie = new Trie(); foreach (string word in new[] { "car", "cart", "cat", "car" }) trie.Add(word);
Console.WriteLine("ca prefix:" + trie.Prefix("ca").ToString().ToLowerInvariant());
Console.WriteLine("ca word:" + trie.Contains("ca").ToString().ToLowerInvariant());
Console.WriteLine("car word:" + trie.Contains("car").ToString().ToLowerInvariant());
Console.WriteLine("empty prefix:" + trie.Prefix("").ToString().ToLowerInvariant());
sealed class Trie {
    private readonly Node root = new();
    public void Add(string word) { Node n=root; foreach(char c in word) { if(!n.Children.TryGetValue(c,out var next)) n.Children[c]=next=new Node(); n=next; } n.Word=true; }
    private Node? Find(string text) { Node n=root; foreach(char c in text) { if(!n.Children.TryGetValue(c,out var next)) return null; n=next; } return n; }
    public bool Prefix(string text) => Find(text) is not null;
    public bool Contains(string text) => Find(text)?.Word == true;
    private sealed class Node { public Dictionary<char,Node> Children { get; } = new(); public bool Word; }
}

Account for time, storage and allocations

For m code units, insertion and lookup take expected O(m) dictionary work, with O(total distinct prefix nodes) retained space. A node can allocate a child dictionary even before many children exist. A fixed alphabet array trades lookup characteristics for potentially much larger sparse storage.

The alphabet and representation drive constants and space. A Dictionary per node supports sparse branching but adds object and hashing overhead. A twenty-six-slot array would need an explicitly limited alphabet; using it for arbitrary UTF-16 input without validation would be both wasteful and incorrect.

Review assumptions and likely defects

Assuming every reached node is a word makes prefix queries accidentally satisfy exact-word checks. Treating char as a user-perceived character changes Unicode semantics. Suggestions also require a separate ordering and result-limit contract; this trie intentionally exposes only existence checks, not a ranked autocomplete system.

Adding normalization during lookup but not insertion would make the representation inconsistent. Deletion also cannot simply remove shared ancestors after clearing a word flag. Any pruning rule must preserve nodes used by another word or by another terminal below the same prefix.

Practice one: discriminate edge cases

Insert the empty word and verify that Contains empty changes while Prefix empty remains true. Hint: there is no character edge to create, so the operation modifies the root. Add a mixed-case word to verify exact matching.

Keep empty-prefix, empty-word and absent-word cases distinct in the assertions. If you insert Car, verify whether car should match under the declared exact-code-unit policy. This gives a concrete check against accidentally introducing culture-sensitive comparison while extending the data structure.

Practice two: defend an extension

Design bounded autocomplete over this structure. Specify ranking, tie order, normalization and maximum returned suggestions before choosing traversal or cached counts. Explain how deleting a word differs from deleting every node on its path when other words share that prefix.

A bounded suggestion API should first choose lexical or popularity order and define how ties are resolved. For lexical order, traversal must visit children in a specified order rather than relying on dictionary enumeration. A result cap bounds returned suggestions but not necessarily the number of visited nodes unless the traversal policy supports early stopping.

Evaluate correctness and interview reasoning

The core proof is path correspondence: following each code unit reaches exactly the node for that prefix, and the terminal flag determines whether the complete word was inserted. The sample exercises a shared prefix, a branching prefix and an idempotent insertion. An effective interview explanation separates that membership problem from autocomplete ranking, normalization and deletion. It also accounts for retained node and dictionary allocations, rather than describing a trie only by the length of one query. This makes the proposed extension measurable instead of quietly changing the meaning of a character or a result order.