Trie (Prefix Tree)
A tree data structure used to store strings efficiently by sharing prefixes. Common in autocomplete, dictionaries, and search suggestions.
Trie (Prefix Tree) Visualization
SlowFast
🔊 Sound
ReadyEmpty Trie. Insert a word.
Active pathFound pathWord end (isEnd)Internal node
empty trie — insert a word
Complexity
Time Complexity:
O(m)Space Complexity:
O(n * alphabet_size)Pseudocode
function insert(root, word):
node = root
for char in word:
if char not in node.children:
node.children[char] = new Node()
node = node.children[char]
mark node as end of word
function search(root, word):
node = root
for char in word:
if char not in node.children:
return false
node = node.children[char]
return node is end of word