Trie (Prefix Tree)
What is a Trie?
A Trie (pronounced "try", from retrieval) is a tree-like data structure used to store strings where each node represents a character. It is optimized for prefix-based searches — finding all words with a given prefix is O(prefix length), not O(n × word length).
- Insert — O(m) where m = word length
- Search — O(m)
- Prefix search — O(m)
- Space — O(ALPHABET_SIZE × m × n) — can be large
Use cases: Autocomplete, spell checkers, IP routing, dictionary implementations, word games.
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
struct TrieNode {
unordered_map<char, TrieNode*> children;
bool isEnd = false;
};
class Trie {
TrieNode* root;
public:
Trie() { root = new TrieNode(); }
void insert(const string& word) {
TrieNode* node = root;
for (char c : word) {
if (!node->children.count(c))
node->children[c] = new TrieNode();
node = node->children[c];
}
node->isEnd = true;
}
bool search(const string& word) {
TrieNode* node = root;
for (char c : word) {
if (!node->children.count(c)) return false;
node = node->children[c];
}
return node->isEnd;
}
bool startsWith(const string& prefix) {
TrieNode* node = root;
for (char c : prefix) {
if (!node->children.count(c)) return false;
node = node->children[c];
}
return true;
}
// Autocomplete: find all words with given prefix
void collectWords(TrieNode* node, string current, vector<string>& results) {
if (node->isEnd) results.push_back(current);
for (auto& [c, child] : node->children)
collectWords(child, current + c, results);
}
vector<string> autocomplete(const string& prefix) {
TrieNode* node = root;
for (char c : prefix) {
if (!node->children.count(c)) return {};
node = node->children[c];
}
vector<string> results;
collectWords(node, prefix, results);
return results;
}
};
int main() {
Trie trie;
for (const string& w : {"apple","app","application","apply","apt","banana"})
trie.insert(w);
cout << boolalpha;
cout << trie.search("app") << endl; // true
cout << trie.search("ap") << endl; // false
cout << trie.startsWith("app") << endl; // true
auto words = trie.autocomplete("app");
cout << "Words with 'app': ";
for (const string& w : words) cout << w << " ";
cout << endl; // app apple application apply
return 0;
}import java.util.*;
public class Trie {
static class TrieNode {
Map<Character, TrieNode> children = new HashMap<>();
boolean isEnd = false;
}
TrieNode root = new TrieNode();
void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
node.children.putIfAbsent(c, new TrieNode());
node = node.children.get(c);
}
node.isEnd = true;
}
boolean search(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (!node.children.containsKey(c)) return false;
node = node.children.get(c);
}
return node.isEnd;
}
boolean startsWith(String prefix) {
TrieNode node = root;
for (char c : prefix.toCharArray()) {
if (!node.children.containsKey(c)) return false;
node = node.children.get(c);
}
return true;
}
List<String> autocomplete(String prefix) {
TrieNode node = root;
for (char c : prefix.toCharArray()) {
if (!node.children.containsKey(c)) return new ArrayList<>();
node = node.children.get(c);
}
List<String> results = new ArrayList<>();
collectWords(node, new StringBuilder(prefix), results);
return results;
}
void collectWords(TrieNode node, StringBuilder current, List<String> results) {
if (node.isEnd) results.add(current.toString());
for (Map.Entry<Character, TrieNode> e : node.children.entrySet()) {
current.append(e.getKey());
collectWords(e.getValue(), current, results);
current.deleteCharAt(current.length() - 1);
}
}
public static void main(String[] args) {
Trie trie = new Trie();
for (String w : new String[]{"apple","app","application","apply","banana"})
trie.insert(w);
System.out.println(trie.search("app")); // true
System.out.println(trie.startsWith("app")); // true
System.out.println(trie.autocomplete("app")); // [app, apple, application, apply]
}
}class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
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):
node = self.root
for c in word:
if c not in node.children: return False
node = node.children[c]
return node.is_end
def starts_with(self, prefix):
node = self.root
for c in prefix:
if c not in node.children: return False
node = node.children[c]
return True
def autocomplete(self, prefix):
node = self.root
for c in prefix:
if c not in node.children: return []
node = node.children[c]
results = []
self._collect(node, prefix, results)
return results
def _collect(self, node, current, results):
if node.is_end: results.append(current)
for c, child in node.children.items():
self._collect(child, current + c, results)
trie = Trie()
for w in ["apple", "app", "application", "apply", "banana"]:
trie.insert(w)
print(trie.search("app")) # True
print(trie.search("ap")) # False
print(trie.starts_with("app")) # True
print(trie.autocomplete("app")) # ['app', 'apple', 'application', 'apply']class TrieNode {
constructor() { this.children = {}; this.isEnd = false; }
}
class Trie {
constructor() { this.root = new TrieNode(); }
insert(word) {
let node = this.root;
for (const c of word) {
if (!node.children[c]) node.children[c] = new TrieNode();
node = node.children[c];
}
node.isEnd = true;
}
search(word) {
let node = this.root;
for (const c of word) {
if (!node.children[c]) return false;
node = node.children[c];
}
return node.isEnd;
}
startsWith(prefix) {
let node = this.root;
for (const c of prefix) {
if (!node.children[c]) return false;
node = node.children[c];
}
return true;
}
autocomplete(prefix) {
let node = this.root;
for (const c of prefix) {
if (!node.children[c]) return [];
node = node.children[c];
}
const results = [];
this._collect(node, prefix, results);
return results;
}
_collect(node, current, results) {
if (node.isEnd) results.push(current);
for (const [c, child] of Object.entries(node.children)) {
this._collect(child, current + c, results);
}
}
}
const trie = new Trie();
["apple","app","application","apply","banana"].forEach(w => trie.insert(w));
console.log(trie.search("app")); // true
console.log(trie.startsWith("app")); // true
console.log(trie.autocomplete("app")); // ['app', 'apple', 'application', 'apply']