Implement Trie (Prefix Tree) — Problem & Solution
Implement Trie (Prefix Tree) solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Implement Trie (Prefix Tree) is a medium coding problem on strings, hash table and trie, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Trie
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A trie (prefix tree) stores a set of strings so that both whole words and prefixes can be looked up quickly — the structure behind autocomplete and spell checkers. Write the class Trie:
Trie()creates an empty trie.void insert(String word)addswordto the trie.boolean search(String word)returnstrueifwordwas inserted before (as a whole word),falseotherwise.boolean startsWith(String prefix)returnstrueif some inserted word begins withprefix,falseotherwise.
The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.
Example 1
Input: ["Trie","insert","search","search","startsWith","insert","search"]
[[],["apple"],["apple"],["app"],["app"],["app"],["app"]]
Output: [null,null,true,false,true,null,true]
Explanation: "app" is a prefix of "apple" but was not inserted as a word, so `search("app")` is false until it is inserted.
Example 2
Input: ["Trie","startsWith","insert","insert","startsWith","search","startsWith"]
[[],["c"],["cat"],["car"],["ca"],["ca"],["cart"]]
Output: [null,false,null,null,true,false,false]
Explanation: Nothing starts with "c" in an empty trie. After "cat" and "car", "ca" is a prefix but not a word, and no word starts with "cart".
Constraints
1 <= word.length, prefix.length <= 2000word and prefix consist only of lowercase English lettersAt most 3 * 10^4 calls are made to insert, search and startsWith
Hints for Implement Trie (Prefix Tree)
Hint 1
Words that share a beginning can share the storage for it: make a tree where each edge is a letter.
Hint 2
Each node has up to 26 children, one per letter, and a flag saying whether some word ends exactly at this node.
Hint 3
Insert walks down from the root, creating missing children. Search and startsWith walk the same path; search additionally needs the end flag on the last node, startsWith only needs the path to exist.
How to solve Implement Trie (Prefix Tree)
Each node of the trie stands for one prefix: the path of letters from the root to it. A node keeps one child per next letter and a flag marking that a whole inserted word ends there.
Approach
insert(word): start at the root; for each letter, move to that child, creating it if missing. Mark the last node as a word end.- Walking a string: start at the root and follow each letter's child; if one is missing, the string is not a prefix of any word.
search(word): walkword; return whether the walk succeeded and the final node is marked as a word end.startsWith(prefix): return whether the walk ofprefixsucceeded.
Why it works
A node exists exactly when its prefix is a prefix of some inserted word, because inserting creates the whole path of a word and nothing else creates nodes. The end flag separates "was inserted" from "is only a prefix" — app and apple share every node of app, and only the flag tells them apart.
Complexity
- Time —
O(L) per operation, L = length of the argument - Space —
O(total letters inserted × alphabet size) for array children
Pitfalls
- Without the end flag,
search("app")would wrongly succeed after inserting onlyapple. - Inserting the same word twice must not create a second path — following existing children takes care of it.
Reference solution
Python
class Trie:
def __init__(self):
self.root = {} # letter -> child node; "$" marks a word end
def insert(self, word: str) -> None:
node = self.root
for ch in word:
node = node.setdefault(ch, {})
node["$"] = True
def _walk(self, s: str):
node = self.root
for ch in s:
node = node.get(ch)
if node is None:
return None
return node
def search(self, word: str) -> bool:
node = self._walk(word)
return node is not None and "$" in node
def startsWith(self, prefix: str) -> bool:
return self._walk(prefix) is not NoneJava
class Trie {
private static class Node {
Node[] next = new Node[26];
boolean end;
}
private Node root = new Node();
public Trie() {
}
public void insert(String word) {
Node node = root;
for (int i = 0; i < word.length(); i++) {
int c = word.charAt(i) - 'a';
if (node.next[c] == null) node.next[c] = new Node();
node = node.next[c];
}
node.end = true;
}
private Node walk(String s) {
Node node = root;
for (int i = 0; i < s.length() && node != null; i++) node = node.next[s.charAt(i) - 'a'];
return node;
}
public boolean search(String word) {
Node node = walk(word);
return node != null && node.end;
}
public boolean startsWith(String prefix) {
return walk(prefix) != null;
}
}C++
class Trie {
struct Node {
Node* next[26] = {};
bool end = false;
};
Node* root = new Node();
Node* walk(const string& s) {
Node* node = root;
for (size_t i = 0; i < s.size() && node; i++) node = node->next[s[i] - 'a'];
return node;
}
public:
Trie() {}
void insert(string word) {
Node* node = root;
for (char ch : word) {
int c = ch - 'a';
if (!node->next[c]) node->next[c] = new Node();
node = node->next[c];
}
node->end = true;
}
bool search(string word) {
Node* node = walk(word);
return node && node->end;
}
bool startsWith(string prefix) {
return walk(prefix) != nullptr;
}
};JavaScript
var Trie = function() {
this.root = { children: {}, end: false };
};
Trie.prototype.insert = function(word) {
var node = this.root;
for (var i = 0; i < word.length; i++) {
var ch = word[i];
if (!node.children[ch]) node.children[ch] = { children: {}, end: false };
node = node.children[ch];
}
node.end = true;
};
Trie.prototype.walk = function(s) {
var node = this.root;
for (var i = 0; i < s.length && node; i++) node = node.children[s[i]];
return node || null;
};
Trie.prototype.search = function(word) {
var node = this.walk(word);
return node !== null && node.end;
};
Trie.prototype.startsWith = function(prefix) {
return this.walk(prefix) !== null;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets