Trie (Prefix Tree) Visualization
A Trie (also called a prefix tree) is a tree-shaped data structure used to store strings. Each node represents a single character, and paths from the root spell out words. It excels at prefix-based lookups — autocomplete, spell-checking, and IP routing all rely on tries. Insertion and search both run in O(L) time, where L is the word length, independent of how many words are stored.
Visualizer
0 word
Pseudocode
function insert(root, word):
node = root
for each char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.isEnd = true
function search(root, word):
node = root
for each char in word:
if char not in node.children:
return false
node = node.children[char]
return node.isEnd
Common Interview Questions
How does Trie differ from a Hash Map for string storage?
A Trie stores strings character-by-character along tree paths, enabling prefix-based queries (autocomplete, starts-with) in O(L) time without scanning all keys. A Hash Map gives O(1) exact lookups but cannot enumerate strings sharing a prefix.
How does deletion in a Trie avoid corrupting shared prefixes?
Use post-order recursion: unmark isEnd at the target word, then delete each ancestor node on the way back up only if it has no remaining children and is not the end of another word. Naively removing entire paths breaks words that share the same prefix.
What are common real-world applications of Tries?
Autocomplete (search engines, IDEs), IP routing via longest-prefix matching (Patricia Tries), spell checkers, and DNA/text pattern search using suffix Tries.
💬 Discussion
to join the discussion
Curious to Learn More?
Hand-picked resources to deepen your understanding
© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0