Trie
Prefix TreeO(k) searchA tree-shaped data structure for storing strings. Each path from root to an end-node spells a word.
Trie pre-populated with preset words. Insert or search!
highlighted
end of word
default
Preset words (click to set)
insert(w)
O(k)
k = word length
search(w)
O(k)
k = word length
prefix(p)
O(k)
Check prefix exists
Space
O(N·k)
N words, avg length k