Approach Summary
Each node has a children map and an isEnd flag. Insert adds nodes char by char. Search/startsWith traverse the trie.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Array-Based 26-Way Trie (Optimal) | O(L) per insert/search/startsWith | O(N * L) | Use fixed 26-element pointer array per node for O(L) time and instant indexing. |
| 2 Approach 2: Hash Map Based Children Nodes (Dynamic Branching) | O(L) per operation | O(Total characters) | Replaces fixed 26-slot array with dynamic hash maps to support arbitrary alphabets and save memory on sparse nodes. |
Step 1: Baseline
Approach 1: Array-Based 26-Way Trie (Optimal)
Time: O(L) per insert/search/startsWith
Space: O(N * L)
Each node contains a fixed array TrieNode[26] where index is char - 'a'. Traversal performs direct array index access in O(1) step time per character.
Approach 1: Array-Based 26-Way Trie (Optimal) Implementation
Approach 1: Array-Based 26-Way Trie (Optimal)
class Trie {
class Node { Node[] c = new Node[26]; boolean end; }
private Node root = new Node();
public void insert(String w) {
Node n = root;
for (char ch : w.toCharArray()) {
if (n.c[ch - 'a'] == null) n.c[ch - 'a'] = new Node();
n = n.c[ch - 'a'];
}
n.end = true;
}
public boolean search(String w) {
Node n = root;
for (char ch : w.toCharArray()) {
if (n.c[ch - 'a'] == null) return false;
n = n.c[ch - 'a'];
}
return n.end;
}
public boolean startsWith(String p) {
Node n = root;
for (char ch : p.toCharArray()) {
if (n.c[ch - 'a'] == null) return false;
n = n.c[ch - 'a'];
}
return true;
}
}class Trie {
struct Node { Node* c[26] = {}; bool end = false; };
Node* root = new Node();
public:
void insert(string w) {
Node* n = root;
for (char ch : w) {
if (!n->c[ch - 'a']) n->c[ch - 'a'] = new Node();
n = n->c[ch - 'a'];
}
n->end = true;
}
bool search(string w) {
Node* n = root;
for (char ch : w) {
if (!n->c[ch - 'a']) return false;
n = n->c[ch - 'a'];
}
return n->end;
}
bool startsWith(string p) {
Node* n = root;
for (char ch : p) {
if (!n->c[ch - 'a']) return false;
n = n->c[ch - 'a'];
}
return true;
}
};class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str):
node = self.root
for c in word:
if c not in node.children: node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word: str) -> bool:
node = self.root
for c in word:
if c not in node.children: return False
node = node.children[c]
return node.is_end
def startsWith(self, prefix: str) -> bool:
node = self.root
for c in prefix:
if c not in node.children: return False
node = node.children[c]
return Trueclass TrieNode {
constructor() { this.c = {}; this.isEnd = false; }
}
class Trie {
constructor() { this.root = new TrieNode(); }
insert(w) {
let n = this.root;
for (const ch of w) { n.c[ch] = n.c[ch] || new TrieNode(); n = n.c[ch]; }
n.isEnd = true;
}
search(w) {
let n = this.root;
for (const ch of w) { if (!n.c[ch]) return false; n = n.c[ch]; }
return n.isEnd;
}
startsWith(p) {
let n = this.root;
for (const ch of p) { if (!n.c[ch]) return false; n = n.c[ch]; }
return true;
}
} Step 2: Most Optimized
Approach 2: Hash Map Based Children Nodes (Dynamic Branching)
Time: O(L) per operation
Space: O(Total characters)
Each node stores a map of characters to child TrieNodes. Nodes only allocate entries for characters that actually occur in inserted words.
Approach 2: Hash Map Based Children Nodes (Dynamic Branching) Implementation
Approach 2: Hash Map Based Children Nodes (Dynamic Branching)
class Trie {
class Node {
Map<Character, Node> children = new HashMap<>();
boolean isEnd = false;
}
private Node root = new Node();
public void insert(String word) {
Node node = root;
for (char c : word.toCharArray()) {
node.children.putIfAbsent(c, new Node());
node = node.children.get(c);
}
node.isEnd = true;
}
public boolean search(String word) {
Node node = root;
for (char c : word.toCharArray()) {
if (!node.children.containsKey(c)) return false;
node = node.children.get(c);
}
return node.isEnd;
}
public boolean startsWith(String prefix) {
Node node = root;
for (char c : prefix.toCharArray()) {
if (!node.children.containsKey(c)) return false;
node = node.children.get(c);
}
return true;
}
}class Trie {
struct Node {
unordered_map<char, Node*> children;
bool isEnd = false;
};
Node* root = new Node();
public:
void insert(string word) {
Node* node = root;
for (char c : word) {
if (!node->children.count(c)) node->children[c] = new Node();
node = node->children[c];
}
node->isEnd = true;
}
bool search(string word) {
Node* node = root;
for (char c : word) {
if (!node->children.count(c)) return false;
node = node->children[c];
}
return node->isEnd;
}
bool startsWith(string prefix) {
Node* node = root;
for (char c : prefix) {
if (!node->children.count(c)) return false;
node = node->children[c];
}
return true;
}
};class Trie:
def __init__(self):
self.root = {}
def insert(self, word: str) -> None:
node = self.root
for ch in word:
if ch not in node:
node[ch] = {}
node = node[ch]
node['#'] = True
def search(self, word: str) -> bool:
node = self.root
for ch in word:
if ch not in node: return False
node = node[ch]
return '#' in node
def startsWith(self, prefix: str) -> bool:
node = self.root
for ch in prefix:
if ch not in node: return False
node = node[ch]
return Trueclass Trie {
constructor() { this.root = {}; }
insert(word) {
let node = this.root;
for (const ch of word) {
if (!node[ch]) node[ch] = {};
node = node[ch];
}
node['#'] = true;
}
search(word) {
let node = this.root;
for (const ch of word) {
if (!node[ch]) return false;
node = node[ch];
}
return Boolean(node['#']);
}
startsWith(prefix) {
let node = this.root;
for (const ch of prefix) {
if (!node[ch]) return false;
node = node[ch];
}
return true;
}
}Edge Cases to Watch
- Empty string or single character word
- Searching for a prefix that is not a registered full word (search returns false, startsWith returns true)
- Multiple words sharing common prefixes (e.g. "app" and "apple")
Algorithmic Pattern
View Pattern Guide →
Master the Trie Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Trie pattern.
How to Recognize This Pattern
- Prefix queries
- Word dictionary design
Complexity Analysis
Time Complexity
O(m) per operation
Space Complexity
O(ALPHABET × n × m)
Tags
Design Trie
Frequently Asked Questions
What is the optimal time and space complexity for Implement Trie (Prefix Tree)?
The optimal solution for Implement Trie (Prefix Tree) achieves O(m) per operation runtime complexity and requires O(ALPHABET × n × m) auxiliary space. Time complexity is O(L) for insert, search, and startsWith operations, where L is the length of the word or prefix. Space complexity is O(N * L) where N is the total number of words and L is the average word length.
How do I identify that Implement Trie (Prefix Tree) requires the Trie pattern?
In technical interviews, look for key problem signals: Prefix queries; Word dictionary design. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Trie strategy.
What critical edge cases must be handled in Implement Trie (Prefix Tree)?
Essential edge cases to verify include: Empty string or single character word; Searching for a prefix that is not a registered full word (search returns false, startsWith returns true); Multiple words sharing common prefixes (e.g. "app" and "apple"). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Implement Trie (Prefix Tree)?
Implement Trie (Prefix Tree) is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Google, Facebook, Microsoft.