The search bar problem
You are building a search bar for a dictionary app. A user types "app" and expects instant suggestions like "apple", "application", and "appetizer". Scanning a list of 100,000 words to find matches starting with "app" feels sluggish. You need a data structure that groups words by their shared prefixes so you can jump straight to the relevant branch. A trie (pronounced "try") does exactly that. It stores strings in a tree where each node represents a character, and paths from the root to marked nodes spell out the words.
How a trie works
Think of a trie like a physical phone book organized by letter. You flip to the "A" section, then the "Ap" subsection, then "App". Each step narrows the scope. In a trie, every node is a character. The root is empty. Its children are the first letters of all words. The children of "A" are the second letters of words starting with "A". If you follow the path A -> P -> P -> L -> E and the final node is marked as a word end, you have found "apple".
The magic is that "apple" and "application" share the nodes for A, P, P, L, I. You store the prefix once, not twice. This sharing makes prefix searches extremely fast. You only traverse the length of the prefix, regardless of how many words are stored. The trade-off is memory. Tries can use more space than a flat list because each node has overhead. You pay memory to buy speed and prefix grouping.
Tries share prefixes. Maps share nothing.
Minimal implementation
Here is the core structure. A node holds a map of children keyed by character and a boolean flag to mark word boundaries. The map allows O(1) lookup for the next character. The flag distinguishes a complete word from a prefix that happens to exist.
// TrieNode holds a map of children and a flag marking the end of a word.
type TrieNode struct {
children map[rune]*TrieNode
isEnd bool
}
// NewTrieNode creates a node with an initialized children map.
// The map must be initialized; a nil map panics on write.
func NewTrieNode() *TrieNode {
return &TrieNode{children: make(map[rune]*TrieNode)}
}
// Insert adds a word to the trie by traversing or creating nodes for each character.
func (root *TrieNode) Insert(word string) {
node := root
for _, char := range word {
// Check if the child exists; create it if missing.
if _, ok := node.children[char]; !ok {
node.children[char] = NewTrieNode()
}
node = node.children[char]
}
// Mark the final node so we know a complete word ends here.
node.isEnd = true
}
// Search returns true if the word exists in the trie.
func (root *TrieNode) Search(word string) bool {
node := root
for _, char := range word {
// Move to the child node if it exists.
if child, ok := node.children[char]; ok {
node = child
} else {
return false
}
}
return node.isEnd
}
The receiver name root is descriptive and follows Go convention. Receiver names are usually one or two letters, but root clarifies the role in tree methods. The fields children and isEnd start with lowercase letters, making them private to the package. This is standard Go style: expose behavior through methods, hide internal state.
Initialize maps. Nil maps panic.
Walking through the logic
Insert "cat". The root node has no child for 'c'. The code creates a new node for 'c' and moves there. The 'c' node has no child for 'a'. Create 'a', move there. The 'a' node has no child for 't'. Create 't', move there. Set isEnd = true. The word "cat" is stored.
Now insert "car". The root has 'c'. Move to 'c'. The 'c' node has 'a'. Move to 'a'. The 'a' node has no 'r'. Create 'r', move there. Set isEnd = true. The 'c' and 'a' nodes are shared between "cat" and "car". You did not duplicate them.
Search "car". Root -> 'c' -> 'a' -> 'r'. The node for 'r' has isEnd = true. Return true. Search "ca". Root -> 'c' -> 'a'. The node for 'a' has isEnd = false. Return false. This correctly distinguishes "ca" from "car". The isEnd flag is essential. Without it, every prefix would be a valid word.
The ok idiom in the map lookup is a Go pattern. val, ok := m[key] returns the value and a boolean indicating presence. If the key is missing, ok is false and val is the zero value. This avoids panics and lets you handle missing keys gracefully.
Finding words with a prefix
Autocomplete requires gathering all words under a prefix. This method finds the prefix node and delegates to a recursive helper. The helper walks the subtree, building up the current path and collecting results when it hits a word end.
// FindAll returns all words in the trie that start with the given prefix.
// It returns nil if the prefix does not exist.
func (root *TrieNode) FindAll(prefix string) []string {
node := root
for _, char := range prefix {
if child, ok := node.children[char]; ok {
node = child
} else {
return nil
}
}
// Collect words from the subtree rooted at the prefix node.
var results []string
collectWords(node, []rune(prefix), &results)
return results
}
// collectWords recursively traverses the trie to gather complete words.
// It appends to the results slice via pointer to avoid copying.
func collectWords(node *TrieNode, path []rune, results *[]string) {
if node.isEnd {
*results = append(*results, string(path))
}
for char, child := range node.children {
// Append the character to the path for the recursive call.
// The child call gets its own copy of the extended path.
collectWords(child, append(path, char), results)
}
}
The helper uses a pointer to the results slice so all recursive calls append to the same backing array. This avoids allocating a new slice at every level. The path slice is passed by value, but append creates a new slice header when capacity is exceeded, so each branch gets its own path without interference. This is a safe recursion pattern.
Recursion gathers words. Iteration finds paths.
Concurrency and safety
In a web server, multiple requests might insert words concurrently. The trie structure itself does not protect against race conditions. Concurrent writes to the map cause panics or corruption. Wrap the trie in a mutex or use a read-write lock.
import "sync"
// ThreadSafeTrie wraps a trie with a read-write mutex for concurrent access.
type ThreadSafeTrie struct {
mu sync.RWMutex
root *TrieNode
}
// NewThreadSafeTrie creates a trie protected by a read-write lock.
func NewThreadSafeTrie() *ThreadSafeTrie {
return &ThreadSafeTrie{root: NewTrieNode()}
}
// Insert locks for writing, adds the word, and unlocks.
func (t *ThreadSafeTrie) Insert(word string) {
t.mu.Lock()
defer t.mu.Unlock()
t.root.Insert(word)
}
// Search locks for reading, checks the word, and unlocks.
func (t *ThreadSafeTrie) Search(word string) bool {
t.mu.RLock()
defer t.mu.RUnlock()
return t.root.Search(word)
}
The sync.RWMutex allows multiple concurrent readers but only one writer. Search operations are common and can run in parallel. Insert operations are exclusive. The defer ensures the lock is released even if a panic occurs. The convention is to name the mutex field mu.
Mutexes protect state. RWMutex allows concurrent reads.
Pitfalls and errors
Forgetting to initialize the map is the most common bug. If NewTrieNode returns &TrieNode{} without make, the children map is nil. Writing to a nil map causes a panic. The runtime crashes with assignment to entry in nil map. Always initialize maps in constructors.
Using byte instead of rune breaks Unicode support. Go strings are UTF-8 sequences. Iterating with range yields runes, which are full Unicode code points. If you index a string with word[i], you get bytes. Multi-byte characters split across indices, corrupting the trie. Stick to range and rune.
Memory overhead can surprise you. Each map entry has overhead. Each node has a struct header. For a trie with millions of words, this adds up. If memory is tight, consider an array of pointers for ASCII characters, or a compressed trie that merges single-child paths. Tries are not always the most memory-efficient structure.
The compiler rejects unused imports. If you add sync for the mutex but forget to use it, you get imported and not used. Remove the import or use the package. The compiler enforces this to keep code clean.
When to use a trie
Use a trie when you need fast prefix searches or autocomplete suggestions. Use a hash map when you only need exact lookups and don't care about prefixes. Use a sorted slice with binary search when memory is constrained and you can tolerate slower prefix scans. Use a radix tree when you want to compress single-child paths to save memory. Use plain sequential code when the dataset is small enough that optimization is premature.
Tries for prefixes. Maps for exact matches.