A trie stores a key one symbol per edge, so all keys with the same prefix share a path. A terminal marker distinguishes a complete key from a prefix. Lookup cost depends on key length, while memory cost depends on the child representation and shared prefixes.
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 x word length).
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']A fixed child array offers constant indexing for a small known alphabet but wastes space in sparse nodes. A map saves empty slots and supports larger alphabets with extra lookup and allocation cost. Define whether input is bytes, Unicode code points, or normalized text before choosing the representation.
Deletion clears the terminal marker and removes ancestors only while they have no children and are not terminal for another key. Autocomplete traverses to the prefix node, then enumerates descendants with a result limit and deterministic ordering.
def trace_trie(items):
print('Input:', items)
for index, value in enumerate(items):
print(f'step={index}, value={value}, remaining={items[index+1:]}')
return len(items)
print('operations:', trace_trie([4, 1, 7, 1]))Each character selects the next edge, so lookup depends mainly on word length.
Nodes may contain many unused child links, especially with a large alphabet.
Mark the terminal node with an end-of-word flag.
Explore 500+ free tutorials across 20+ languages and frameworks.