Learn
Trie (Prefix Tree)
A Trie, also known as a prefix tree or digital tree, stores strings so that all strings with a common prefix share the same path from the root. This makes prefix queries run in time where is the prefix length.
Each node contains an array of children (one per character) and a count of how many words pass through that node.
class TrieNode:
children = array of size 26, initialized to null
prefixCount = 0
function insert(root, word):
node = root
for each char c in word:
index = c - 'a'
if node.children[index] is null:
node.children[index] = new TrieNode()
node = node.children[index]
node.prefixCount = node.prefixCount + 1
function countPrefix(root, prefix):
node = root
for each char c in prefix:
index = c - 'a'
if node.children[index] is null:
return 0
node = node.children[index]
return node.prefixCount
How prefixCount works: Every time you insert a word, you increment the count at each node along the path. The count tells you how many inserted words pass through that node.
Memory optimization: For sparse tries with many possible characters, you use a hash map instead of a fixed-size array for children.
Applications: You use Tries for autocomplete, spell checkers, IP routing tables, and word games like Boggle.
Time complexity: per operation where is the string length.