Introduction

A trie, or prefix tree, is a data structure built for storing strings by shared prefixes instead of storing each string independently. It is especially useful when you need fast prefix queries such as autocomplete, dictionary lookup, or routing-table style matching. The main complexity result is that operations depend on key length rather than the total number of stored words.

How a Trie Stores Data

Each edge in a trie represents one character, and each path from the root corresponds to a prefix. A node often contains:

• a mapping from character to child node
• a flag indicating whether a full word ends at that node

Here is a simple Python implementation:

1class TrieNode:
2    def __init__(self):
3        self.children = {}
4        self.is_word = False
5
6
7class Trie:
8    def __init__(self):
9        self.root = TrieNode()
10
11    def insert(self, word: str) -> None:
12        node = self.root
13        for ch in word:
14            node = node.children.setdefault(ch, TrieNode())
15        node.is_word = True
16
17    def search(self, word: str) -> bool:
18        node = self.root
19        for ch in word:
20            if ch not in node.children:
21                return False
22            node = node.children[ch]
23        return node.is_word
24
25    def starts_with(self, prefix: str) -> bool:
26        node = self.root
27        for ch in prefix:
28            if ch not in node.children:
29                return False
30            node = node.children[ch]
31        return True

This is the standard shape behind most trie discussions.

Search Complexity

Searching for a word of length m takes O(m) time because the algorithm follows at most one edge per character.

That is the key trie idea: lookup does not depend directly on how many total words are stored, only on how long the query is.

Example:

1trie = Trie()
2for word in ["tree", "trie", "trap", "try"]:
3    trie.insert(word)
4
5print(trie.search("trie"))   # True
6print(trie.search("trip"))   # False
7print(trie.starts_with("tr"))  # True

If the searched word is not present, failure can happen before processing all characters, but worst-case complexity is still O(m).

Insert and Delete Complexity

Insertion is also O(m) for a word of length m, because each character is processed once.

Deletion is slightly more involved because nodes may need to be cleaned up only if they are no longer shared by other words.

1class Trie(Trie):
2    def delete(self, word: str) -> bool:
3        def _delete(node, i):
4            if i == len(word):
5                if not node.is_word:
6                    return False, False
7                node.is_word = False
8                return True, len(node.children) == 0
9
10            ch = word[i]
11            if ch not in node.children:
12                return False, False
13
14            deleted, remove_child = _delete(node.children[ch], i + 1)
15            if remove_child:
16                del node.children[ch]
17
18            should_remove = not node.is_word and len(node.children) == 0
19            return deleted, should_remove
20
21        deleted, _ = _delete(self.root, 0)
22        return deleted

Deletion still has O(m) traversal cost, though cleanup logic adds implementation complexity.

Prefix Queries Are Where Tries Shine

A trie is most compelling when you care about prefixes, not just exact words. Once you reach the node for a prefix, every descendant represents a completion.

Simple prefix collection:

1def collect_words(node, prefix, out):
2    if node.is_word:
3        out.append(prefix)
4    for ch, child in node.children.items():
5        collect_words(child, prefix + ch, out)
6
7
8def autocomplete(trie, prefix):
9    node = trie.root
10    for ch in prefix:
11        if ch not in node.children:
12            return []
13        node = node.children[ch]
14
15    out = []
16    collect_words(node, prefix, out)
17    return out
18
19
20print(autocomplete(trie, "tr"))

Exact search and prefix search both start with the same O(m) traversal, which is why tries are popular for autocomplete engines.

Space Complexity and Tradeoffs

The main downside of a trie is memory usage. If you store many sparse branches, the child maps at each node can consume much more memory than a hash set of complete words.

Approximate considerations:

• time for search and insert: O(m)
• memory: proportional to total number of characters stored across all nodes

In practice, space usage depends heavily on alphabet size and representation. An array of fixed child pointers is fast but wasteful for sparse alphabets. A dictionary of children is more memory-efficient but slightly slower.

When a Trie Is Better Than a Hash Set

Use a trie when you need:

• prefix search
• autocomplete
• lexicographic traversal
• longest-prefix matching

Use a hash set when you need only exact membership checks and want simpler code with lower memory overhead.

That distinction matters more than theoretical lookup complexity alone.

Common Pitfalls

• Assuming trie lookup is O(1) just because it feels tree-like.
• Ignoring memory cost when storing large sparse alphabets.
• Forgetting the end-of-word marker and treating prefixes as full words.
• Using a trie when a hash set would be simpler for exact-only lookup.
• Overlooking cleanup logic when implementing delete.

Summary

• Trie operations scale with key length, usually O(m).
• Search, insert, and prefix lookup all follow one edge per character.
• Prefix queries are the main reason to choose a trie.
• The tradeoff is increased memory usage compared with simpler structures.
• Choose node representation based on alphabet size and workload.