Implement Trie (Prefix Tree)
Asked at Google, Meta, Amazon, Microsoft, Apple, Uber
Problem
Implement a trie with insert, search, and startsWith methods. A trie is a tree-like data structure for storing strings where each node represents a character.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Amazon | Medium | View all Amazon questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Apple | Medium | View all Apple questions → |
| Uber | Medium | View all Uber questions → |
How to Think About It
Each node has a dictionary of children (char → node) and a boolean flag marking the end of a word.
Insert: traverse char by char, creating child nodes as needed. Mark the last node as end-of-word.
Search: traverse char by char. Return true only if all characters are found AND the last node is marked as end-of-word.
StartsWith: same as search, but return true if traversal completes (don't check the end-of-word flag).
Why trie over hash set: trie supports prefix queries efficiently. Hash set can't answer "does any word start with X?" without checking every word.
Visual walkthrough for insert "cat":
root → create child 'c' → node_c
node_c → create child 'a' → node_ca
node_ca → create child 't' → node_cat
Mark node_cat as end-of-word.
Search "cat": traverse c→a→t, check is_end → true.
Search "ca": traverse c→a, check is_end → false (not a complete word).
StartsWith "ca": traverse c→a → true (prefix exists).
Edge cases: empty string insert/search, single character words, words that are prefixes of other words.
Optimal Approach
class TrieNode:
children = {} # char → TrieNode
is_end = False
insert(word): for each char, create child if missing, move down. Mark is_end at last char.
search(word): for each char, return false if missing. Return is_end of last node.
startsWith(prefix): for each char, return false if missing. Return true if traversal completes.
Time: O(m) per operation where m is word/prefix length. Space: O(total characters across all words).
What Trips People Up in Real Interviews
Confusing "trie" with "binary tree." A trie node has up to 26 children (one per letter), not 2.
Forgetting to mark the end of a word. Without is_end, you can't distinguish between a prefix and a complete word.
Not creating child nodes during insert. If a child doesn't exist, create it before moving down.
Confusing "startsWith" with "search." startsWith returns true if any word has the prefix. search returns true only if the exact word exists.
Implementing the Trie with a fixed-size array of 26 children instead of a dictionary. Arrays waste space for sparse tries; a dictionary (char → node) is more memory-efficient for inputs with few distinct characters.
Solution Code
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, word):
node = self.root
for ch in word:
if ch not in node.children:
return False
node = node.children[ch]
return node.is_end
def startsWith(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children:
return False
node = node.children[ch]
return TrueFrequently Asked Questions
What is the Implement Trie (Prefix Tree) problem?
Implement a `trie` with insert, search, and startsWith methods. A `trie` is a tree-like data structure for storing strings where each node represents a character.
How do you solve Implement Trie (Prefix Tree)?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Implement Trie (Prefix Tree)?
Implement Trie (Prefix Tree) is asked at Google, Meta, Amazon, Microsoft, Apple, Uber. It is a medium difficulty problem.
What are common mistakes on Implement Trie (Prefix Tree)?
- Confusing "`trie`" with "binary tree." A `trie` node has up to 26 children (one per letter), not 2.
- Forgetting to mark the end of a word. Without is_end, you can't distinguish between a prefix and a complete word.
- Not creating child nodes during insert. If a child doesn't exist, create it before moving down.
- Confusing "startsWith" with "search." startsWith returns `true` if any word has the prefix. search returns `true` only if the exact word exists.
- Implementing the `Trie` with a fixed-size array of 26 children instead of a dictionary. Arrays waste space for sparse `trie`s; a dictionary (char → node) is more memory-efficient for inputs with few distinct characters.