What is a Trie?
Learn what a trie (prefix tree) is, how it enables fast autocomplete and prefix search, and how to answer this interview question.
Expected Interview Answer
A trie, or prefix tree, is a tree-based data structure that stores strings character by character along shared paths, letting you search, insert, and check prefixes in O(m) time where m is the string length, independent of how many strings are stored.
Each node represents a character and holds child pointers for possible next characters plus a flag marking whether a complete word ends there. Strings sharing a common prefix share the same path from the root, which makes prefix lookups and autocomplete extremely fast since you only walk down, never scan the full dataset. This is why tries power autocomplete, spell checkers, and IP routing tables. The tradeoff is memory: a trie can use more space than a hash set because of all the child pointers, especially with sparse alphabets.
- O(m) lookup regardless of dataset size
- Efficient prefix queries and autocomplete
- Shared storage for common prefixes
- No hashing collisions to worry about
AI Mentor Explanation
A trie is like a coaching manual organized by shot type, where “drive” branches into “cover drive”, “straight drive”, and “on drive”, all sharing the same first five letters as one path in the book. Looking up any shot starting with “dri” means flipping to one shared section instead of scanning the whole manual for every shot name. A flag at the end of “cover drive” marks that it is a complete, named shot rather than just a fragment. This shared-prefix structure is exactly why a trie answers “what shots start with cov” instantly, without checking every shot in the coaching book.
Step-by-Step Explanation
Step 1
Start at the root
The root node represents the empty string and has no character of its own.
Step 2
Insert character by character
Walk or create a child node for each character; mark the final node as end-of-word.
Step 3
Search by walking the path
Follow child pointers for each character; if any is missing, the string is not present.
Step 4
Prefix query walks then explores
Walk to the prefix’s final node, then traverse its subtree to collect all completions.
What Interviewer Expects
- Explain nodes represent characters, not whole strings
- State O(m) time complexity, independent of number of stored strings
- Give real use cases: autocomplete, spell check, IP routing
- Acknowledge the memory tradeoff vs hash sets
Common Mistakes
- Confusing a trie with a binary search tree
- Forgetting the end-of-word marker, causing false positive prefix matches
- Claiming O(1) lookup instead of O(m) where m is string length
- Not mentioning the memory overhead of many child pointers per node
Best Answer (HR Friendly)
“A trie is a tree that stores words letter by letter, so words sharing the same start also share the same path in the tree. It is what makes autocomplete and spell-check features feel instant, since finding matches only means walking down the tree rather than checking every word.”
Code Example
class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False
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_word = True
def search(self, word):
node = self._walk(word)
return node is not None and node.is_word
def starts_with(self, prefix):
return self._walk(prefix) is not None
def _walk(self, s):
node = self.root
for ch in s:
if ch not in node.children:
return None
node = node.children[ch]
return nodeFollow-up Questions
- How would you implement autocomplete on top of a trie?
- How does a trie compare to a hash set for prefix-based search?
- How would you reduce a trie’s memory usage (e.g. compressed trie / radix tree)?
- How would you delete a word from a trie without breaking other words?
MCQ Practice
1. What is the time complexity of searching for a word of length m in a trie?
Search walks one node per character of the word, giving O(m), independent of how many words are stored.
2. What does the end-of-word marker in a trie node indicate?
The marker distinguishes a complete stored word from a node that is only part of a longer word’s path.
3. Which use case is a trie best suited for?
Shared prefixes as shared tree paths make tries ideal for autocomplete, spell check, and prefix queries.
Flash Cards
What does each node in a trie typically represent? — A single character, with children for possible next characters.
What is the time complexity of trie search? — O(m), where m is the length of the string, regardless of dataset size.
Name two real-world uses of a trie. — Autocomplete/search suggestions and spell checking (also IP routing tables).
What is the main memory tradeoff of a trie? — It can use more memory than a hash set due to many child pointers per node.