aloalgoTrie Implementation
A trie consists of nodes, where each node contains a map of children (character → child node) and a flag indicating if it's the end of a word.TrieNode Class
Trie Class
Example Usage
Visualizing Insert
Alternative: Array-Based Children
For lowercase letters only, you can use an array of size 26 instead of a dictionary. This is faster but uses more memory.Complexity
- Insert: O(m) where m = word length
- Search: O(m) where m = word length
- StartsWith: O(m) where m = prefix length
- Space: O(n * m) where n = number of words, m = average word length
Common Interview Tips
- Use a helper method: The _find_node helper avoids code duplication between search and startsWith.
- Dictionary vs Array: Use dictionary for mixed characters, array for lowercase-only (faster).
- Don't forget is_end: This distinguishes complete words from prefixes.
Was this helpful?
Company
Practice
© 2026 aloalgo. All rights reserved.