Implement Trie (Prefix Tree)
Asked at Google, Meta, Amazon, Microsoft and 2 more
Difficulty
Medium
Time
O(m) per operation
Space
O(total characters inserted)
Pattern
Trie
Companies
6
Problem
Design a data structure called a trie (also called a prefix tree). It stores a set of strings and lets you answer three kinds of questions quickly.
You must support three operations. insert(word) adds a word to the trie. search(word) returns true only if that exact word was inserted before. startsWith(prefix) returns true if at least one inserted word begins with the given prefix.
The trie is a tree where each node stands for one character. A path from the root spells a string. Each node also carries a flag that says "a word ends here". That flag is the only difference between search and startsWith: both walk the same path, but search also checks the flag at the final node.
One tree, two kinds of questions
Constraints
- ●
1 <= word.length, prefix.length <= 2000 - ●
word and prefix consist only of lowercase English letters - ●
At most 3 * 10^4 calls in total to insert, search, and startsWith
Examples
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]][null, null, true, false, true, null, true]["Trie", "insert", "search", "startsWith"]
[[], ["cat"], ["ca"], ["ca"]][null, null, false, true]Asked At
6 companies| 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.
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).
Insert "app" after "apple"
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
O(m) per operation timeclass 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 runs in O(m) per operation time and O(total characters inserted) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.