Implement Trie (Prefix Tree)
Problem
Implement a trie with insert, search, and startsWith methods to store and query strings efficiently.
- 1 ≤ word.length, prefix.length ≤ 2000
- word and prefix consist only of lowercase English letters
- At most 3 * 10⁴ calls will be made to insert, search, and startsWith
Example
insert("apple"), search("apple"), search("app"), startsWith("app"), insert("app"), search("app")null, true, false, true, null, trueFirst, "apple" is inserted into the trie. Searching for "apple" returns true because it was inserted. Searching for "app" returns false because "app" was not inserted as a complete word. startsWith("app") returns true because "apple" starts with "app". Then "app" is inserted. Searching for "app" now returns true.
Approach
Straightforward Solution
A naive approach would store all words in a list and perform linear scans for search and prefix queries, resulting in O(n*m) time per query (n = number of words, m = length of word/prefix), which is inefficient for large datasets.
Core Observation
A trie is a tree-like data structure where each node represents a character and paths from the root to nodes represent prefixes of inserted words. This structure enables efficient prefix-based queries by sharing common prefixes among words.
Path to Optimal
The key recognition signals are 'insert', 'search', and 'startsWith' operations on strings, which indicate a Trie pattern. Tries optimize prefix queries by structuring words as paths in a tree, enabling O(m) time complexity per operation, where m is the length of the word or prefix. Each node stores children nodes keyed by characters, and a boolean flag marks the end of a word. This allows quick traversal and early termination when a prefix or word is not found.
Optimal Approach
Implement a TrieNode class with a dictionary mapping characters to child nodes and a boolean flag for end-of-word. The Trie class maintains a root node. Insert iterates through characters, creating nodes as needed. Search and startsWith traverse nodes according to input characters, returning true or false based on presence and end-of-word flags. This approach guarantees efficient prefix and exact word queries with O(m) time per operation.
Time
O(m)
Each operation (insert, search, startsWith) processes each character of the input string once, resulting in linear time proportional to the length of the word or prefix.
Space
O(n * m)
In the worst case, all inserted words are distinct with no shared prefixes, requiring storage proportional to the total number of characters across all words. Each node stores a dictionary of children, which can grow with the alphabet size and number of unique prefixes.
Pattern Spotlight
Trie (Prefix Tree)
Tries represent sets of strings as paths in a tree, enabling O(m) time prefix and exact match queries by sharing common prefixes and marking word boundaries explicitly.
Solution
| 1 | class TrieNode: |
| 2 | def __init__(self): |
| 3 | self.children = {} |
| 4 | self.end_of_word = False |
| 5 | |
| 6 | class Trie: |
| 7 | def __init__(self): |
| 8 | self.root = TrieNode() |
| 9 | |
| 10 | def insert(self, word: str) -> None: |
| 11 | curr = self.root |
| 12 | for c in word: |
| 13 | if c not in curr.children: |
| 14 | curr.children[c] = TrieNode() |
| 15 | curr = curr.children[c] |
| 16 | curr.end_of_word = True |
| 17 | |
| 18 | def search(self, word: str) -> bool: |
| 19 | curr = self.root |
| 20 | for c in word: |
| 21 | if c not in curr.children: |
| 22 | return False |
| 23 | curr = curr.children[c] |
| 24 | return curr.end_of_word |
| 25 | |
| 26 | def startsWith(self, prefix: str) -> bool: |
| 27 | curr = self.root |
| 28 | for c in prefix: |
| 29 | if c not in curr.children: |
| 30 | return False |
| 31 | curr = curr.children[c] |
| 32 | return True |
| 1 | import java.util.HashMap; |
| 2 | import java.util.Map; |
| 3 | |
| 4 | class TrieNode { |
| 5 | Map<Character, TrieNode> children = new HashMap<>(); |
| 6 | boolean endOfWord = false; |
| 7 | } |
| 8 | |
| 9 | public class Trie { |
| 10 | private final TrieNode root; |
| 11 | |
| 12 | public Trie() { |
| 13 | root = new TrieNode(); |
| 14 | } |
| 15 | |
| 16 | public void insert(String word) { |
| 17 | TrieNode curr = root; |
| 18 | for (char c : word.toCharArray()) { |
| 19 | if (!curr.children.containsKey(c)) { |
| 20 | curr.children.put(c, new TrieNode()); |
| 21 | } |
| 22 | curr = curr.children.get(c); |
| 23 | } |
| 24 | curr.endOfWord = true; |
| 25 | } |
| 26 | |
| 27 | public boolean search(String word) { |
| 28 | TrieNode curr = root; |
| 29 | for (char c : word.toCharArray()) { |
| 30 | if (!curr.children.containsKey(c)) { |
| 31 | return false; |
| 32 | } |
| 33 | curr = curr.children.get(c); |
| 34 | } |
| 35 | return curr.endOfWord; |
| 36 | } |
| 37 | |
| 38 | public boolean startsWith(String prefix) { |
| 39 | TrieNode curr = root; |
| 40 | for (char c : prefix.toCharArray()) { |
| 41 | if (!curr.children.containsKey(c)) { |
| 42 | return false; |
| 43 | } |
| 44 | curr = curr.children.get(c); |
| 45 | } |
| 46 | return true; |
| 47 | } |
| 48 | } |
| 1 | #include <unordered_map> |
| 2 | #include <string> |
| 3 | |
| 4 | using namespace std; |
| 5 | |
| 6 | class TrieNode { |
| 7 | public: |
| 8 | unordered_map<char, TrieNode*> children; |
| 9 | bool end_of_word = false; |
| 10 | |
| 11 | TrieNode() = default; |
| 12 | ~TrieNode() { |
| 13 | for (auto& pair : children) { |
| 14 | delete pair.second; |
| 15 | } |
| 16 | } |
| 17 | }; |
| 18 | |
| 19 | class Trie { |
| 20 | private: |
| 21 | TrieNode* root; |
| 22 | |
| 23 | public: |
| 24 | Trie() { |
| 25 | root = new TrieNode(); |
| 26 | } |
| 27 | |
| 28 | ~Trie() { |
| 29 | delete root; |
| 30 | } |
| 31 | |
| 32 | void insert(const string& word) { |
| 33 | TrieNode* curr = root; |
| 34 | for (char c : word) { |
| 35 | if (curr->children.find(c) == curr->children.end()) { |
| 36 | curr->children[c] = new TrieNode(); |
| 37 | } |
| 38 | curr = curr->children[c]; |
| 39 | } |
| 40 | curr->end_of_word = true; |
| 41 | } |
| 42 | |
| 43 | bool search(const string& word) { |
| 44 | TrieNode* curr = root; |
| 45 | for (char c : word) { |
| 46 | if (curr->children.find(c) == curr->children.end()) { |
| 47 | return false; |
| 48 | } |
| 49 | curr = curr->children[c]; |
| 50 | } |
| 51 | return curr->end_of_word; |
| 52 | } |
| 53 | |
| 54 | bool startsWith(const string& prefix) { |
| 55 | TrieNode* curr = root; |
| 56 | for (char c : prefix) { |
| 57 | if (curr->children.find(c) == curr->children.end()) { |
| 58 | return false; |
| 59 | } |
| 60 | curr = curr->children[c]; |
| 61 | } |
| 62 | return true; |
| 63 | } |
| 64 | }; |
| 1 | class TrieNode { |
| 2 | constructor() { |
| 3 | this.children = new Map(); |
| 4 | this.endOfWord = false; |
| 5 | } |
| 6 | } |
| 7 | |
| 8 | class Trie { |
| 9 | constructor() { |
| 10 | this.root = new TrieNode(); |
| 11 | } |
| 12 | |
| 13 | insert(word) { |
| 14 | let curr = this.root; |
| 15 | for (const c of word) { |
| 16 | if (!curr.children.has(c)) { |
| 17 | curr.children.set(c, new TrieNode()); |
| 18 | } |
| 19 | curr = curr.children.get(c); |
| 20 | } |
| 21 | curr.endOfWord = true; |
| 22 | } |
| 23 | |
| 24 | search(word) { |
| 25 | let curr = this.root; |
| 26 | for (const c of word) { |
| 27 | if (!curr.children.has(c)) { |
| 28 | return false; |
| 29 | } |
| 30 | curr = curr.children.get(c); |
| 31 | } |
| 32 | return curr.endOfWord; |
| 33 | } |
| 34 | |
| 35 | startsWith(prefix) { |
| 36 | let curr = this.root; |
| 37 | for (const c of prefix) { |
| 38 | if (!curr.children.has(c)) { |
| 39 | return false; |
| 40 | } |
| 41 | curr = curr.children.get(c); |
| 42 | } |
| 43 | return true; |
| 44 | } |
| 45 | } |
Step-by-Step Solution
Build TrieNode Structure to Represent Characters and Word Endings
| 2 | def __init__(self): |
| 3 | self.children = {} |
| 4 | self.end_of_word = False |
Objective
To create a node structure that holds child nodes for each character and a flag indicating if the node marks the end of a word.
Key Insight
Each TrieNode acts as a branching point in the trie, with a dictionary mapping characters to child nodes enabling dynamic and sparse storage. The end_of_word flag is essential to differentiate between nodes that represent prefixes and those that represent complete words. This design supports efficient traversal and word boundary detection.
Interview Quick-Check
Core Logic
TrieNode stores children in a dictionary keyed by characters and a boolean flag to mark word completion.
Common Pitfalls & Bugs
Forgetting to initialize the children dictionary or the end_of_word flag leads to incorrect trie behavior.
Initialize Trie with a Root Node
| 6 | class Trie: |
| 7 | def __init__(self): |
| 8 | self.root = TrieNode() |
Objective
To set up the Trie data structure with a root node that serves as the starting point for all operations.
Key Insight
The root node represents an empty prefix and anchors the trie. All insertions and searches begin from this node, ensuring a consistent entry point. This abstraction hides the complexity of the trie from the user and centralizes traversal logic.
Interview Quick-Check
Core Logic
The root node is an empty TrieNode that serves as the origin for all insert, search, and prefix operations.
Insert Words by Creating or Traversing Child Nodes
| 10 | def insert(self, word: str) -> None: |
| 11 | curr = self.root |
| 12 | for c in word: |
| 13 | if c not in curr.children: |
| 14 | curr.children[c] = TrieNode() |
| 15 | curr = curr.children[c] |
| 16 | curr.end_of_word = True |
Objective
To add words to the trie by iterating through each character and creating nodes as needed.
Key Insight
Insertion walks down the trie following existing nodes for each character. When a character is missing, a new node is created, extending the trie. Marking the final node's end_of_word flag signals the completion of a valid word. This incremental construction ensures shared prefixes are stored once, optimizing space and enabling efficient queries.
Interview Quick-Check
Core Logic
Insert traverses or creates nodes for each character and marks the last node as end_of_word to represent a complete word.
Common Pitfalls & Bugs
Failing to mark the end_of_word flag after insertion causes search to incorrectly report missing words.
Search for Exact Words by Traversing Nodes and Checking End Flags
| 18 | def search(self, word: str) -> bool: |
| 19 | curr = self.root |
| 20 | for c in word: |
| 21 | if c not in curr.children: |
| 22 | return False |
| 23 | curr = curr.children[c] |
| 24 | return curr.end_of_word |
Objective
To determine if a word exists in the trie by following nodes for each character and verifying the end_of_word flag.
Key Insight
Search traverses the trie character by character. If any character is missing, the word does not exist. If traversal completes, the end_of_word flag confirms whether the path corresponds to a complete word or just a prefix. This distinction is crucial for correctness.
Interview Quick-Check
Core Logic
Search returns true only if all characters are found sequentially and the final node is marked as end_of_word.
Common Pitfalls & Bugs
Returning true without checking end_of_word can cause false positives for prefixes that are not complete words.
Check Prefix Existence by Traversing Nodes Without End Flag Requirement
| 26 | def startsWith(self, prefix: str) -> bool: |
| 27 | curr = self.root |
| 28 | for c in prefix: |
| 29 | if c not in curr.children: |
| 30 | return False |
| 31 | curr = curr.children[c] |
| 32 | return True |
Objective
To verify if any word in the trie starts with a given prefix by traversing nodes for each prefix character.
Key Insight
Unlike search, startsWith only requires that the prefix path exists in the trie. It does not check the end_of_word flag because prefixes need not be complete words. This allows efficient prefix queries by early termination if any character is missing.
Interview Quick-Check
Core Logic
startsWith returns true if all prefix characters are found sequentially in the trie, regardless of end_of_word flags.
Common Pitfalls & Bugs
Using the wrong variable name (e.g., 'word' instead of 'prefix') in the loop can cause runtime errors or incorrect results.
Line Analysis
This solution has 1 Critical line interviewers watch for.
self.children = {}Create an empty dictionary to hold child nodes keyed by characters.
Using a dictionary allows efficient O(1) average lookup and insertion of child nodes for each character, supporting sparse and dynamic branching.
def __init__(self):Define the TrieNode initializer.
The TrieNode initializer defines the per-node state every trie operation depends on, so it establishes the node contract before any traversal or insertion begins.
self.end_of_word = FalseInitialize the end_of_word flag to False, indicating this node does not yet represent a complete word.
This flag is essential to distinguish nodes that represent prefixes from those that mark the end of inserted words.
class Trie:Define the Trie class that will manage the root node and provide insert, search, and prefix methods.
Encapsulating trie operations within a class provides a clean interface and maintains the root node as the entry point.
def __init__(self):Initialize the Trie with a root TrieNode representing the empty prefix.
The root node anchors the trie and serves as the starting point for all traversals and insertions.
self.root = TrieNode()Assign a new TrieNode instance to the root attribute.
This ensures the trie starts empty with no children, ready to accept insertions.
def insert(self, word: str) -> None:Begin the insert method to add a word to the trie.
This method implements the core logic for building the trie structure by adding new words.
curr = self.rootStart traversal from the root node.
All insertions begin at the root, ensuring consistent construction of the trie.
for c in word:Iterate over each character in the input word.
Processing characters sequentially allows building or traversing the path representing the word.
if c not in curr.children:Check if the current character is not already a child of the current node.
This condition detects when a new branch must be created to represent a previously unseen prefix.
curr.children[c] = TrieNode()Create a new TrieNode for the current character and add it to the children dictionary.
This extends the trie by adding a new node for the character, enabling future traversals and insertions.
curr = curr.children[c]Move the current pointer to the child node corresponding to the current character.
Advancing the pointer allows continuing the insertion or traversal along the word's path.
curr.end_of_word = TrueMark the current node as the end of a word after processing all characters.
This flag signals that the path from root to this node represents a complete inserted word, differentiating it from mere prefixes.
def search(self, word: str) -> bool:Begin the search method to check if a word exists in the trie.
This method implements exact word lookup by traversing the trie.
curr = self.rootStart traversal from the root node.
All searches begin at the root to ensure consistent lookup.
for c in word:Iterate over each character in the input word.
Sequential character processing allows traversal along the word's path.
if c not in curr.children:Check if the current character is not a child of the current node.
If a character is missing, the word cannot exist in the trie, enabling early termination.
return FalseReturn False immediately if the character is missing.
This early return prevents unnecessary traversal and correctly indicates the word is absent.
curr = curr.children[c]Move the current pointer to the child node for the current character.
Advancing the pointer continues traversal along the word's path.
return curr.end_of_wordReturn True if the current node marks the end of a word, False otherwise.
This final check distinguishes between a complete word and a prefix, ensuring accurate search results.
def startsWith(self, prefix: str) -> bool:Begin the startsWith method to check if any word starts with the given prefix.
This method enables prefix queries by traversing the trie.
curr = self.rootStart traversal from the root node.
All prefix checks begin at the root for consistent traversal.
for c in prefix:Iterate over each character in the prefix.
Sequential character processing allows traversal along the prefix path.
if c not in curr.children:Check if the current character is not a child of the current node.
If a character is missing, no word with the prefix exists, enabling early termination.
return FalseReturn False immediately if the character is missing.
This early return prevents unnecessary traversal and correctly indicates no word starts with the prefix.
curr = curr.children[c]Move the current pointer to the child node for the current character.
Advancing the pointer continues traversal along the prefix path.
return TrueReturn True after successfully traversing all prefix characters.
If traversal completes without missing characters, the prefix exists in the trie.
Test Your Understanding
Why does the Trie use a boolean flag at nodes instead of just relying on the presence of children to determine if a word exists?
Because a node can be both a prefix of longer words and a complete word itself, the boolean flag explicitly marks the end of a valid inserted word, distinguishing between prefixes and full words.
Related Problems
Tries pattern
Don't just read it. Drill it.
Reconstruct Implement Trie (Prefix Tree) from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Implement Trie (Prefix Tree) drill