What is a trie, and how does it work?
A trie (prefix tree) is a tree for storing strings in which each edge represents one character and each path from the root spells a prefix. Words that share a prefix share the same path, and a node is marked with an is_end flag when a complete word ends there. Insert, search and prefix checks all take O(L) time for a string of length L, independent of how many words are stored, which makes tries ideal for prefix queries such as autocomplete.
Read full answerHide full answer
Applies toautocomplete and search suggestions, spell checkers, IP routing (longest prefix match), word games, dictionary and prefix-counting problems
Structure
Words: car, cat, cart, dog
(root)
├── c
│ └── a
│ ├── r* (car)
│ │ └── t* (cart)
│ └── t* (cat)
└── d
└── o
└── g* (dog)
* marks is_end = True. The prefix ca is stored once and shared by three words.
Implementation in Python
class TrieNode:
def __init__(self):
self.children = {} # char -> TrieNode
self.is_end = False # True if a word ends here
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_end = True
def _find(self, s):
node = self.root
for ch in s:
node = node.children.get(ch)
if node is None:
return None
return node
def search(self, word):
node = self._find(word)
return node is not None and node.is_end
def starts_with(self, prefix):
return self._find(prefix) is not None
t = Trie()
for w in ["car", "cat", "cart", "dog"]:
t.insert(w)
print(t.search("car"), t.search("ca"), t.starts_with("ca"), t.search("cow"))
# True False True False
search("ca") is False because ca is only a prefix, not a stored word; starts_with("ca") is True.
Complexity
| Operation | Time | Notes |
|---|---|---|
| Insert | O(L) | Creates at most L new nodes |
| Search | O(L) | Follows L edges |
Prefix check (starts_with) |
O(P) | P = prefix length |
| List words with a prefix | O(P + size of the output subtree) | |
| Space | O(total characters) nodes; up to O(total characters x alphabet) with fixed-size child arrays |
Using a dict of children stores only the edges that exist, which saves a lot of space compared with a fixed array of 26 (or 256) slots per node when nodes have few children.
Why Use a Trie
-
Prefix queries are natural: all words with a prefix sit in one subtree.
-
Lexicographic order: a depth-first traversal visiting children in sorted order yields words in sorted order.
-
Shared prefixes reduce repeated work (for example checking many words against a grid in Word Search II).
-
Predictable time: O(L) regardless of dictionary size, with no hash collisions.
Limitations
-
Memory overhead: one node per character, each with its own children map; often more memory than a hash set of strings.
-
Poor cache locality with pointer-based nodes.
-
For exact-match lookups only, a hash table is usually simpler and faster.
Variants (Briefly)
-
Compressed trie / radix tree: merges chains of single-child nodes into one edge labelled with a string.
-
Suffix trie / suffix tree: stores all suffixes of a text for fast substring search.
-
Ternary search tree: each node has less, equal and greater children; less memory than wide tries.
-
Bitwise (binary) trie: stores numbers bit by bit; used for maximum XOR and IP routing.
Interview Tip
Define a trie as a prefix tree with one character per edge and an is_end flag, write insert, search and starts_with, and give O(L) complexity. Mentioning the dict-of-children space saving and the radix-tree variant shows depth.