trie.definition
trie.descriptionPart1
trie.descriptionPart2
trie.keyPointsTitle
- trie.keyPoint1
- trie.keyPoint2
- trie.keyPoint3
- trie.keyPoint4
trie.exampleTitle
root
c
c
d
d
a
a
o
o
t
t
r
r
g
g
trie.exampleCaption
Regular Node
End of Word
trie.syntaxTitle
// Java
class TrieNode {
TrieNode[] children = new TrieNode[36];
boolean isEndOfWord = false;
}
class Trie {
TrieNode root = new TrieNode();
void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int i = getIndex(c);
if (node.children[i] == null)
node.children[i] = new TrieNode();
node = node.children[i];
}
node.isEndOfWord = true;
}
boolean search(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int i = getIndex(c);
if (node.children[i] == null) return false;
node = node.children[i];
}
return node.isEndOfWord;
}
}# Python
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word: str) -> bool:
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word// C++
class TrieNode {
public:
TrieNode* children[36] = {nullptr};
bool isEndOfWord = false;
};
class Trie {
TrieNode* root = new TrieNode();
public:
void insert(string word) {
TrieNode* node = root;
for (char c : word) {
int i = getIndex(c);
if (!node->children[i])
node->children[i] = new TrieNode();
node = node->children[i];
}
node->isEndOfWord = true;
}
bool search(string word) {
TrieNode* node = root;
for (char c : word) {
int i = getIndex(c);
if (!node->children[i]) return false;
node = node->children[i];
}
return node->isEndOfWord;
}
};// JavaScript
class TrieNode {
constructor() {
this.children = new Map();
this.isEndOfWord = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (const char of word) {
if (!node.children.has(char))
node.children.set(char, new TrieNode());
node = node.children.get(char);
}
node.isEndOfWord = true;
}
search(word) {
let node = this.root;
for (const char of word) {
if (!node.children.has(char)) return false;
node = node.children.get(char);
}
return node.isEndOfWord;
}
}trie.visualization
🌲
Trie is empty. Insert a word or use Random Words to begin.
Words: 0Nodes: 0
Node
Visiting
Found
Inserting
Removing
End of Word
Note: Each node represents a character. Green ring indicates end of a word. Words sharing prefixes share the same path from root.
Time & Space Complexity
| Operation | Time | Space | Description |
|---|---|---|---|
| Insert | O(m) | O(m) | Traverse/create nodes for each character |
| Search | O(m) | O(1) | Traverse nodes matching each character |
| Delete | O(m) | O(1) | Find word, remove marker, cleanup unused nodes |
| Prefix Search | O(p) | O(1) | Traverse to prefix end, p = prefix length |
| Autocomplete | O(p + k) | O(k) | Find prefix, collect k matching words |
m = word length: Operations depend on the length of the word being processed, not the total number of words stored.
Total space: O(ALPHABET_SIZE × m × n) worst case, where n = number of words, m = average word length.
Advantage: Operations are independent of how many words are stored, making Tries efficient for large dictionaries.
trie.continueLearning
enhanced.author.title
enhanced.author.writtenBy:enhanced.author.teamName
enhanced.author.reviewedBy:enhanced.author.reviewerName
enhanced.author.lastUpdated:February 3, 2026