Trie Operations
Trie supports three main operations: insert, search, and startsWith (prefix search). Each operation runs in O(L) time where L is the length of the word or prefix.
Insert a word:
Start at root, for each character, go to child node (create if absent). After last character, mark node as end of word.
public void insert(String word) {
TrieNode curr = root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (curr.children[idx] == null) curr.children[idx] = new TrieNode();
curr = curr.children[idx];
}
curr.isEndOfWord = true;
}
Search for a word:
Traverse the characters; if any missing or the last node not marked end, return false.
public boolean search(String word) {
TrieNode curr = root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (curr.children[idx] == null) return false;
curr = curr.children[idx];
}
return curr.isEndOfWord;
}
StartsWith (prefix search):
Similar to search but does not require end-of-word flag.
public boolean startsWith(String prefix) {
TrieNode curr = root;
for (char c : prefix.toCharArray()) {
int idx = c - 'a';
if (curr.children[idx] == null) return false;
curr = curr.children[idx];
}
return true;
}
Two Minute Drill
- Insert: O(L) time, creates nodes for new characters.
- Search: O(L) time, checks existence and end-of-word.
- StartsWith: O(L) time, checks prefix existence.
- Space: O(total characters * alphabet size) but often compressed.
Need more clarification?
Drop us an email at career@quipoinfotech.com