Tries

Why tries exist (motivation)

Hash tables are great when you want to answer: “Is this exact key present?” in about O(1) average time. But they’re not naturally built for questions like:

• •“List all keys with prefix p.”
• •“How many keys start with p?”
• •“What’s the longest prefix of this query that exists in the dictionary?”

You can do these with hashing, but you typically need extra indexing, sorting, or scanning.

A trie is designed around prefix structure. It stores many strings such that shared prefixes are represented once, then branch when the next character differs.

Definition (prefix tree)

A trie is a rooted tree where:

1. 1)Edges are labeled by characters.
2. 2)Each node corresponds to the prefix formed by concatenating edge labels along the path from the root.
3. 3)A node can be marked as terminal (and/or store a value) to indicate that the prefix at that node is a complete stored key.

If the root represents the empty prefix "", then following edges labeled 'c' → 'a' → 't' leads you to a node representing the prefix "cat".

The atomic concepts in one picture (mentally)

• •Path-prefix representation: path labels define prefixes.
• •Character-labeled branching: next character chooses the next edge.
• •Terminal marker: distinguishes keys from mere prefixes.

This last point is crucial: if you store "car" and "cart", then the node for "car" is terminal, while it also has a child edge 't'.

Complexity intuition: why O(k)?

Operations on tries are usually measured in terms of the string length.

Let k be the length of a key. Search/insert/delete walk one character at a time. That’s k steps.

So:

• •Search(key): O(k)
• •Insert(key): O(k)
• •Delete(key): O(k)

This is not “always faster” than hash tables—constant factors matter—but it’s predictably proportional to key length, and it enables efficient prefix queries.

Data model: child_map

Each node needs a way to get from a character to the child node.

We’ll refer to this as:

• •child_map : character → child node

Typical representations:

The trie’s headline O(k) assumes child lookup is O(1) (array or hash map). If you use a tree-map, you get O(k log Σ).

What tries store (set vs map)

A trie can store:

• •A set of strings: each terminal node has a boolean isTerminal.
• •A map from string → value: each terminal node stores value (or pointer to value).

Both variants are common; the mechanics are the same.

Why this mechanic is the heart of a trie

Tries are powerful because they turn string comparison into shared traversal.

In a sorted list, to compare two strings you scan until they differ. In a trie, you physically share that scanned prefix: once a prefix exists as a path, every key with that prefix reuses it.

Building the idea slowly

Suppose we insert these keys:

• •"to"
• •"tea"
• •"ten"
• •"in"
• •"inn"

Start at the root (""), then:

• •"to": root —'t'→ node("t") —'o'→ node("to") and mark node("to") terminal.
• •"tea": root —'t'→ node("t") already exists, then 'e' creates node("te"), then 'a' creates node("tea"), mark terminal.

Notice how "to" and "tea" share the node("t").

Terminal marker: distinguishing key vs prefix

A trie node represents a prefix, but not every prefix is a stored key.

Example: insert "tea" only.

• •node("t") exists
• •node("te") exists
• •node("tea") exists and is terminal

Now search for "te": you can walk 't' then 'e' and arrive at node("te"). If you didn’t have a terminal marker, you might incorrectly conclude "te" is present. Terminal markers make the answer precise.

Formally:

• •A key s is stored iff the node reached by following s exists and isTerminal = true.

How this enables prefix queries

Let p be a prefix. If you can traverse p (character by character) to reach node(p), then:

• •Every key with prefix p is in the subtree rooted at node(p).

This is the key property that hash tables don’t naturally provide.

Counting and aggregation (a common extension)

Often, nodes store extra metadata to answer queries efficiently:

• •prefixCount: how many keys pass through this node
• •terminalCount: how many keys end here (useful for multisets)

Then:

• •number of keys with prefix p = prefixCount at node(p)

This is not required for basic tries, but it’s a frequent real-world upgrade.

Time complexity: stating it carefully

Let k = |s| be the number of characters.

Traversal visits exactly k edges, doing a child_map lookup at each step.

So the work is:

∑ (per-character child lookup)

If child lookup is O(1) average:

O(k)

If child lookup is O(log Σ):

O(k log Σ)

Where Σ is alphabet size (e.g., 26 lowercase, 128 ASCII, or full Unicode codepoints).

Memory: the trade you’re making

Tries often use more memory than a hash table for the same set of strings, because you store nodes and child maps.

But they compress shared prefixes. If your dataset has lots of common prefixes (URLs, file paths, dictionary words, identifiers), a trie can be surprisingly memory-competitive and faster for prefix operations.

Why focus on mechanics

A trie is simple conceptually, but correctness depends on a few details:

• •When to create nodes
• •How to mark terminal nodes
• •How to delete without breaking other keys

We’ll describe operations for a trie that stores a set of strings with isTerminal.

Search(s)

Intuition

To search s, follow the unique path dictated by its characters. If at any character you can’t follow the edge, the string isn’t stored.

Algorithm

1. 1)Start at root.
2. 2)For each character c in s:

• •If c ∉ node.child_map: return false
• •Else node = node.child_map[c]

3. 3)After consuming all characters: return node.isTerminal

Complexity

• •Visits k characters → O(k)

Insert(s)

Intuition

Insertion is just “create missing edges along the path, then mark the endpoint terminal.” If the path already exists, you only update the terminal marker.

Algorithm

1. 1)Start at root.
2. 2)For each character c in s:

• •If c ∉ child_map: create new node, set child_map[c] = new node
• •node = child_map[c]

3. 3)Set node.isTerminal = true

Complexity

• •O(k) time
• •Up to k new nodes created (worst case)

Delete(s)

Why deletion is trickier

If you delete "inn" but keep "in", you must not remove the shared prefix nodes. You only remove nodes that become unreachable from any terminal key.

A standard approach:

1. 1)Traverse to the end node.
2. 2)If it’s not terminal, nothing to delete.
3. 3)Unmark terminal.
4. 4)Walk back up the path and remove nodes that now have:

• •no children, and
• •are not terminal

This is basically garbage-collecting dead suffix nodes.

A careful delete strategy (stack of nodes)

During traversal, store the path:

• •A stack of (parentNode, charUsed) pairs

Then after unmarking terminal, pop upward:

• •Let child be the node you just processed.
• •If child has 0 children and child.isTerminal is false, remove it from its parent’s child_map.
• •Stop as soon as a node either has other children or is terminal.

Complexity

• •Traversal down: O(k)
• •Cleanup up to k steps: O(k)

So delete is O(k) time.

Subtle but important: representing characters

If your alphabet is ASCII letters, an array of size 26 or 52 might be great.

If your keys are arbitrary Unicode strings, a sparse map is safer.

This choice affects constants and memory but not the core idea.

Comparing with hash tables (when would you choose a trie?)

A useful mindset: a trie is an indexing structure for strings where structure matters (prefixes), not just equality.

Autocomplete (classic application)

Autocomplete is the canonical trie use-case:

1. 1)Traverse the user-typed prefix p to node(p).
2. 2)Enumerate keys in the subtree.

To enumerate keys:

• •Do a DFS/BFS from node(p).
• •Maintain a growing string (or store parent pointers to reconstruct).
• •Every time you visit a terminal node, output the accumulated string.

If you need “top-k suggestions,” you often store extra info at nodes (e.g., most frequent completions, or a heap of top terms).

Longest prefix match (routing, tokenization)

Given a query string q, you may want the longest prefix of q that exists as a key.

Traverse characters until you can’t continue, tracking the last terminal node you saw.

This shows up in:

• •IP routing tables (in a bitwise trie)
• •Lexers/tokenizers (match longest keyword/operator)

Prefix counts and analytics

If each node tracks prefixCount (how many inserted strings pass through), then you can answer:

• •“How many words start with p?” in O(|p|)

Update rule during insert:

• •At each visited node, do prefixCount += 1

Delete similarly decrements.

Variants you should know exist (even if you don’t implement them yet)

Tradeoffs and practical guidance

• •If you need many prefix queries or lexicographic iteration: trie is a strong default.
• •If you only need exact membership and values: hash table is usually simpler and faster.
• •If memory becomes an issue: consider a compact trie (radix tree) or store children in sorted arrays.

A note on “O(k) independent of n”

A key selling point is that lookup doesn’t scale with the number of stored strings n the same way many other structures do.

• •In a balanced BST keyed by full strings, compare cost can be O(k), and you do O(log n) comparisons ⇒ O(k log n).
• •In a trie, you do O(k) character steps.

That said, enumeration from a prefix node can output many results; the time necessarily scales with how many keys you return.