Trie

An autocomplete box must answer more than exact membership. Given the fragment lap, it needs every stored key that begins there. A hash map hashes the whole key and has no location for a shared prefix, so this query scans all n keys. A trie keys the set by the sequence of characters. The prefix becomes a node in the structure rather than a filter over every entry.

Each edge is labelled with a single character. The path from the root to a node spells a prefix, which means keys are represented by paths, not stored explicitly at the nodes. Every node carries a child map (or a fixed array with one slot per alphabet symbol) and an end-of-word flag marking where a complete key terminates. Words that share a prefix share the same path until they diverge: car, card, and care all reuse the c → a → r route and only branch at the fourth character.

What the structure gives up is compactness. Every distinct prefix becomes a node: a sparse child map stores only actual branches but pays for a map and node object at each prefix, while a fixed child array avoids hashing by reserving σ slots per node. Recovering a full key from a node requires retaining its traversal path or storing parent links, because the node itself holds only outgoing branches and an end marker.

Core shape: strings → character-labelled edges from one root → a path spells a prefix → an end-of-word flag marks a complete key

VisualizationVisualizationComplexityComplexity

Visualization

Representation and Invariants

A node holds two pieces of state and nothing else:

• A mapping from the next character to a child node — a Dictionary<char, Node> when the alphabet is open or sparse, or a fixed Node[σ] array indexed by symbol when the alphabet is small and known (children[c - 'a']).
• A boolean IsEnd flag that is true exactly when the path from the root to this node is a stored key.

The key itself is never stored. card exists in the trie when the edges c, a, r, d can all be followed from the root and the node reached at d has IsEnd set. The same walk without the final flag check answers a prefix query: reaching the node is enough, because it certifies that at least one stored key starts with the fragment.

Three invariants hold in a valid trie:

1. The path from the root to any node spells the prefix that every key beneath that node shares. A node is reachable by exactly one character sequence.
2. IsEnd on a node is independent of whether that node has children. car and card coexist: the r node is both an end-of-word and an interior node on the way to d.
3. Insertion only ever adds nodes or sets a flag; it never relabels an existing edge, so previously inserted keys stay reachable.

The distinction between reaching a node and reaching a flagged node is the whole contract: exact search checks the flag, prefix search does not.

Complexity

TimeSpace

• Insert (key length l): O(l)
• Search / StartsWith: O(l)
• Delete: O(l)
• Prefix collection: O(l + v + c)

σ

alphabet size

c

total output characters copied

l

length of the inserted or queried key

h

maximum trie height or longest remaining suffix

u

number of distinct stored prefixes and therefore trie nodes

v

number of trie nodes visited beneath the matched prefix

When Fixed Child Arrays Hurt

The wasted memory is structural, not incidental. An array-backed node reserves σ child slots even when a node has one child, so a long chain of single-character branches — the tail of a rare word — allocates a nearly empty array at every step.

The same layout fixes the alphabet at construction. An array-indexed trie using children[c - 'a'] silently breaks on uppercase, digits, Unicode, or emoji: the index lands outside the 26-slot array or aliases the wrong slot. The character domain has to be decided up front, and input normalized (for example, lower-cased) identically on insert and query, or the two operations walk different paths for the same word.

A trie pays off when the key has a useful symbol sequence and the workload queries that sequence — strings, byte sequences, IP prefixes, or integers treated as bit strings for longest-prefix matching. Opaque IDs queried only by exact equality gain nothing from the prefix structure. For that workload, a hash map fits.

Deletion is the operation that exposes the shared-path invariant. Removing car when card is also present must clear the r node’s IsEnd flag but leave the node itself, because d still hangs off it. Pruning may only remove nodes that have become both unflagged and childless, walking back up until that condition fails. Implementations that skip the prune and merely tombstone the flag leak nodes under churn.

Diagram and C# Implementation

Shared-prefix paths for car, card, care

graph TD
  R((root)) -->|c| C[c]
  C -->|a| A[a]
  A -->|r| RR["r ✓"]
  RR -->|d| D["d ✓"]
  RR -->|e| E["e ✓"]

A check mark marks an end-of-word node. The r node is flagged (the key car) and also an interior node on the way to card and care.

C# implementation

public sealed class Trie
{
    private sealed class Node
    {
        public readonly Dictionary<char, Node> Children = new();
        public bool IsEnd;
    }
 
    private readonly Node _root = new();
 
    public void Insert(string word)
    {
        var node = _root;
        foreach (var c in word)
        {
            if (!node.Children.TryGetValue(c, out var next))
            {
                node.Children[c] = next = new Node();
            }
 
            node = next;
        }
 
        node.IsEnd = true;
    }
 
    public bool Search(string word) => Walk(word) is { IsEnd: true };
 
    public bool StartsWith(string prefix) => Walk(prefix) is not null;
 
    private Node? Walk(string s)
    {
        var node = _root;
        foreach (var c in s)
        {
            if (!node.Children.TryGetValue(c, out var next))
            {
                return null;
            }
 
            node = next;
        }
 
        return node;
    }
}

Search and StartsWith share the same walk. The only difference is that Search requires the terminal node’s IsEnd flag while StartsWith accepts any reached node. A Dictionary child map keeps memory proportional to actual branches. A Node[26] array is faster per step but reserves all slots.

Comparison

Every structure below stores a set of keys. They differ in whether prefixes and ordering survive, and in memory.

Structure	Exact membership	Prefix / ordered support	Storage shape	Stronger case
Trie	Walks one edge per key character	Native prefix walk. Sorted output when children are visited in symbol order	One node per distinct prefix. Sparse maps or fixed child arrays	Autocomplete, routing, and shared-prefix key sets
Hash map	Hashes the complete key	No native prefix or ordered scan	One entry per complete key	Membership-only workloads
Radix / PATRICIA trie	Compares compressed edge labels	Native prefix walk. Sorted output requires symbol-ordered edges	Compresses single-child runs but retains edge-label data	Long sparse keys where plain-trie node count dominates
Aho-Corasick	Retains every pattern in a trie	Scans text for many patterns through failure links	Trie nodes plus failure and output links	Matching many patterns against the same text

A hash map wins when only exact membership matters and memory is tight: it drops prefix and ordering entirely and avoids a node per distinct prefix. A radix tree is the trie to pick when the plain trie’s node count is the problem — it compresses single-child chains without changing the query semantics. Aho-Corasick extends the trie with failure links to scan one text against many patterns at once, a different workload from single-key lookup.

References

• PATRICIA — Practical Algorithm To Retrieve Information Coded In Alphanumeric
• Tries