A trie stores strings character-by-character in a tree, where each edge represents a character. Shared prefixes share the same path, making prefix lookups very fast.
Use when: you need prefix matching, autocomplete, spell checking, or efficient string set operations.
Each node has up to 26 children (for lowercase a-z) and a flag marking if a complete word ends here.
Insert adds a word by walking/creating nodes for each character. Time: O(m) where m is the word length.
Search returns true if the exact word exists.
StartsWith returns true if any word in the trie has the given prefix. Same as Search but doesn’t require isEnd to be true.
Trace: Insert “app”, “apple”, “api”
“app”: root -> a -> p -> p (end) “apple”: root -> a -> p -> p -> l -> e (end) “api”: root -> a -> p -> i (end) ^– shared prefix “ap”
Search(“app”) = true (p.isEnd = true) Search(“ap”) = false (p.isEnd = false) StartsWith(“ap”) = true (node exists)
type TrieNode struct {
children [26]*TrieNode
isEnd bool
}
type Trie struct {
root *TrieNode
}
func NewTrie() *Trie {
return &Trie{root: &TrieNode{}}
}
func (t *Trie) Insert(word string) {
node := t.root
for _, ch := range word {
idx := ch - 'a'
if node.children[idx] == nil {
node.children[idx] = &TrieNode{}
}
node = node.children[idx]
}
node.isEnd = true
}
func (t *Trie) Search(word string) bool {
node := t.root
for _, ch := range word {
idx := ch - 'a'
if node.children[idx] == nil {
return false
}
node = node.children[idx]
}
return node.isEnd
}
func (t *Trie) StartsWith(prefix string) bool {
node := t.root
for _, ch := range prefix {
idx := ch - 'a'
if node.children[idx] == nil {
return false
}
node = node.children[idx]
}
return true
}
func main() {
t := NewTrie()
t.Insert("app")
t.Insert("apple")
t.Insert("api")
fmt.Println("Search app: ", t.Search("app"))
fmt.Println("Search ap: ", t.Search("ap"))
fmt.Println("Prefix ap: ", t.StartsWith("ap"))
fmt.Println("Search banana:", t.Search("banana"))
fmt.Println("Prefix ban: ", t.StartsWith("ban"))
}