Stage 1 · Code
Advanced Data Structures
Trie
Prefix tree for autocomplete, spell check, and IP routing.
6 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode
Trie Structure
A Trie (prefix tree) stores strings as paths from root to leaf. Each node represents a prefix. Children are indexed by character. Node stores: children map, isEndOfWord flag.
Gotrie-implementation.go
49 linesLn 1, Col 1Go
Fixed array of 26 for lowercase a-z. For general Unicode, use map[rune]*TrieNode. Insert: traverse/create nodes, mark end. Search: traverse, check isEnd. Prefix: traverse, return true if path exists.
Core Operations
| Operation | Time | Space |
|---|---|---|
| Insert | O(L) | O(L) new nodes |
| Search | O(L) | O(1) |
| Prefix check | O(L) | O(1) |
| Delete | O(L) | O(1) |
Applications
- Autocomplete: Find all words with given prefix (DFS from prefix node).
- Spell check: Check if word exists; suggest corrections by traversing.
- IP routing: Longest prefix match for IP forwarding tables.
- Dictionary: Word validation, prefix counting.
- XOR problems: Maximum XOR of two numbers in array using binary trie.
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.