Implement Trie (Prefix Tree)
Implement Trie (Prefix Tree) is a medium tries problem solved with the basics pattern.
The best approach, optimal (trie nodes with 26 children), runs in O(L) per operation time and O(total characters · 26) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from hash set of words up.
Problem
Implement a trie (prefix tree) with three operations: insert(word), search(word) (was this exact word inserted?) and startsWith(prefix) (was any word with this prefix inserted?).
Examples
Example 1
- Input
insert("apple"); search("apple"); search("app"); startsWith("app"); insert("app"); search("app")- Output
true, false, true, true
Constraints
- Words and prefixes use lowercase letters, length 1 to 2000.
- Up to
3 * 10^4calls.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (1 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Hash set of words | O(n · L) for startsWith | O(total characters) |
| Optimal (trie nodes with 26 children) | O(L) per operation | O(total characters · 26) |
1Hash set of words
O(n · L) for startsWithO(total characters)Store the words in a set. search is O(L) on average, but startsWith must scan every word.
- insert: add to set. search: contains.
- startsWith: check each word's prefix.
class Trie {
private final Set<String> words = new HashSet<>();
public void insert(String word) { words.add(word); }
public boolean search(String word) { return words.contains(word); }
public boolean startsWith(String prefix) {
for (String w : words) if (w.startsWith(prefix)) return true;
return false;
}
}class Trie:
def __init__(self):
self.words: Set[str] = set()
def insert(self, word: str) -> None:
self.words.add(word)
def search(self, word: str) -> bool:
return word in self.words
def startsWith(self, prefix: str) -> bool:
for w in self.words:
if w.startswith(prefix):
return True
return Falseclass Trie {
unordered_set<string> words;
public:
void insert(string word) { words.insert(word); }
bool search(string word) { return words.count(word) > 0; }
bool startsWith(string prefix) {
for (const string& w : words) if (w.compare(0, prefix.size(), prefix) == 0) return true;
return false;
}
};class Trie {
constructor() { this.words = new Set(); }
insert(word) { this.words.add(word); }
search(word) { return this.words.has(word); }
startsWith(prefix) {
for (const w of this.words) if (w.startsWith(prefix)) return true;
return false;
}
}2Optimal (trie nodes with 26 children)
O(L) per operationO(total characters · 26)Walk down one node per character, creating nodes on insert. search needs the walk to succeed and the final node to be marked as a word end; startsWith only needs the walk to succeed.
- insert: for each char, create the child if missing; move; mark end.
- search: walk; return node != null && node.end.
- startsWith: walk; return node != null.
class Trie {
private static class Node {
Node[] next = new Node[26];
boolean end;
}
private final Node root = new Node();
public void insert(String word) {
Node cur = root;
for (char c : word.toCharArray()) {
if (cur.next[c - 'a'] == null) cur.next[c - 'a'] = new Node();
cur = cur.next[c - 'a'];
}
cur.end = true;
}
public boolean search(String word) {
Node n = walk(word);
return n != null && n.end;
}
public boolean startsWith(String prefix) {
return walk(prefix) != null;
}
private Node walk(String s) {
Node cur = root;
for (char c : s.toCharArray()) {
cur = cur.next[c - 'a'];
if (cur == null) return null;
}
return cur;
}
}class Node:
def __init__(self):
self.next: List[Optional["Node"]] = [None] * 26
self.end = False
class Trie:
def __init__(self):
self.root = Node()
def insert(self, word: str) -> None:
cur = self.root
for c in word:
i = ord(c) - ord('a')
if cur.next[i] is None:
cur.next[i] = Node()
cur = cur.next[i]
cur.end = True
def search(self, word: str) -> bool:
n = self.walk(word)
return n is not None and n.end
def startsWith(self, prefix: str) -> bool:
return self.walk(prefix) is not None
def walk(self, s: str) -> Optional[Node]:
cur = self.root
for c in s:
cur = cur.next[ord(c) - ord('a')]
if cur is None:
return None
return curclass Trie {
struct Node {
Node* next[26] = {};
bool end = false;
};
Node* root = new Node();
public:
void insert(string word) {
Node* cur = root;
for (char c : word) {
if (cur->next[c - 'a'] == nullptr) cur->next[c - 'a'] = new Node();
cur = cur->next[c - 'a'];
}
cur->end = true;
}
bool search(string word) {
Node* n = walk(word);
return n != nullptr && n->end;
}
bool startsWith(string prefix) {
return walk(prefix) != nullptr;
}
private:
Node* walk(const string& s) {
Node* cur = root;
for (char c : s) {
cur = cur->next[c - 'a'];
if (cur == nullptr) return nullptr;
}
return cur;
}
};class Node {
constructor() {
this.next = new Array(26).fill(null);
this.end = false;
}
}
class Trie {
constructor() { this.root = new Node(); }
insert(word) {
let cur = this.root;
for (let i = 0; i < word.length; i++) {
const c = word.charCodeAt(i) - 97;
if (cur.next[c] === null) cur.next[c] = new Node();
cur = cur.next[c];
}
cur.end = true;
}
search(word) {
const n = this.walk(word);
return n !== null && n.end;
}
startsWith(prefix) {
return this.walk(prefix) !== null;
}
walk(s) {
let cur = this.root;
for (let i = 0; i < s.length; i++) {
cur = cur.next[s.charCodeAt(i) - 97];
if (cur === null) return null;
}
return cur;
}
}Edge cases to test
- A word that is a prefix of another (app vs apple)
- search for a prefix that exists but is not a full word
Hints
Hint 1
Each node has 26 child slots and a flag that marks the end of a word.
FAQ
What is the best time complexity for Implement Trie (Prefix Tree)?
Optimal (trie nodes with 26 children) runs in O(L) per operation time and O(total characters · 26) extra space.
Which pattern does Implement Trie (Prefix Tree) use?
It is a tries problem that uses the basics pattern. Other problems with the same pattern: Implement Trie ll, Design In-Memory File System, Design Search Autocomplete System.
Is there a brute force solution for Implement Trie (Prefix Tree)?
Yes. Hash set of words takes O(n · L) for startsWith time and O(total characters) space. Store the words in a set.
Which edge cases should I test for Implement Trie (Prefix Tree)?
A word that is a prefix of another (app vs apple); search for a prefix that exists but is not a full word.