12. Tries

A trie (pronounced "try") is a tree where each path from root to node represents a prefix. Instead of storing complete keys in each node like a BST, a trie stores one character per edge. This makes prefix operations — "find all words starting with 'pre'" — trivially fast.

The Structure

Each node has up to 26 children (for lowercase English) and a flag marking whether a complete word ends here.

type TrieNode struct {
    Children [26]*TrieNode
    IsEnd    bool
}

type Trie struct {
    Root *TrieNode
}

func NewTrie() *Trie {
    return &Trie{Root: &TrieNode{}}
}

Why [26]*TrieNode instead of map[rune]*TrieNode?

Even with most slots nil, the array is smaller and faster. A nil pointer is just 8 zero bytes — no heap allocation, no GC tracking. The map is only worth it if the alphabet is large (Unicode) or truly unbounded. For interview problems (a-z only), [26] is the standard.

Inserting "cat" and "car":

        root
         |
         c
         |
         a
        / \
       t   r
      (✓)  (✓)

"ca" is a prefix of both. "cat" and "car" are complete words.

Core Operations

LeetCode 208 - Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

// Insert a word — O(m) where m is word length
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
}

// Search for exact word — O(m)
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
}

// Check if any word starts with prefix — O(m)
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
}

Every operation is O(m) where m is the length of the word/prefix. Independent of how many words are stored. A hash map gives O(m) lookup too (hashing the string is O(m)), but can't do prefix queries.

Delete Operation

Deleting from a trie requires removing nodes that are no longer part of any word. Recurse to the end of the word, unmark IsEnd, then backtrack — removing nodes that have no children and aren't end-of-word for another entry.

func (t *Trie) Delete(word string) {
    t.deleteHelper(t.Root, word, 0)
}

func (t *Trie) deleteHelper(node *TrieNode, word string, depth int) bool {
    if node == nil {
        return false
    }
    if depth == len(word) {
        node.IsEnd = false
        return !hasChildren(node) // delete node if no children
    }
    idx := word[depth] - 'a'
    shouldDelete := t.deleteHelper(node.Children[idx], word, depth+1)
    if shouldDelete {
        node.Children[idx] = nil
        return !node.IsEnd && !hasChildren(node)
    }
    return false
}

func hasChildren(node *TrieNode) bool {
    for _, child := range node.Children {
        if child != nil {
            return true
        }
    }
    return false
}

The key insight: only remove a node if it has no children AND isn't the end of another word. "car" and "card" share the path c→a→r — deleting "car" unmarks IsEnd on 'r' but doesn't remove the node because 'd' still needs it.

Wildcard Matching

The '.' wildcard matches any single character. Instead of following one path, try all 26 children at that position.

func (t *Trie) SearchWithWildcard(word string) bool {
    return t.matchHelper(t.Root, word, 0)
}

func (t *Trie) matchHelper(node *TrieNode, word string, depth int) bool {
    if node == nil {
        return false
    }
    if depth == len(word) {
        return node.IsEnd
    }
    ch := word[depth]
    if ch == '.' {
        // Try all children
        for _, child := range node.Children {
            if child != nil && t.matchHelper(child, word, depth+1) {
                return true
            }
        }
        return false
    }
    return t.matchHelper(node.Children[ch-'a'], word, depth+1)
}

This is what makes tries powerful for pattern matching — a hash map can't do "find all words matching c.t" without checking every key.

Pattern: Autocomplete

Find all words with a given prefix. Navigate to the prefix node, then DFS to collect all words below it.

func (t *Trie) Autocomplete(prefix string) []string {
    node := t.Root
    for _, ch := range prefix {
        idx := ch - 'a'
        if node.Children[idx] == nil {
            return nil // no words with this prefix
        }
        node = node.Children[idx]
    }
    // DFS from this node to find all complete words
    var results []string
    var dfs func(n *TrieNode, path string)
    dfs = func(n *TrieNode, path string) {
        if n.IsEnd {
            results = append(results, path)
        }
        for i, child := range n.Children {
            if child != nil {
                dfs(child, path+string(rune('a'+i)))
            }
        }
    }
    dfs(node, prefix)
    return results
}

This is what powers search bars, IDE completions, and command-line tab completion.

Pattern: Word Validation

Check if a string can be built from a dictionary of words. Tries make this efficient when the dictionary is large and you're checking many strings.

Dictionary: ["app", "apple", "application", "apt"]

Trie lets you check "does any word start with 'app'?" in O(3)
instead of scanning all dictionary entries.

Trie vs Hash Map vs BST

*Hash computation is O(m). **Must check every key. k = number of results.

Tries win decisively for prefix operations. They lose on memory — each node has 26 pointers (or a map for larger alphabets).

Real-World Uses

Autocomplete — search engines, IDEs, command lines. Type a prefix, get suggestions instantly.

Spell checkers — check if a word exists, suggest corrections by exploring nearby paths.

IP routing — longest prefix match on binary tries. Router looks up "192.168.1.5" by walking the trie bit by bit.

DNS resolution — domain names are hierarchical strings, naturally trie-shaped.

T9 predictive text — old phone keyboards mapped digits to letters, tries found valid words.

Variants

Compressed trie (radix tree) — merge single-child chains into one node. "application" doesn't need 11 nodes if no other word shares the prefix beyond "app". Saves memory.

Ternary search trie — each node has three children (less, equal, greater). Uses less memory than a 26-way trie for sparse alphabets.

When to Use Tries

• Prefix matching and autocomplete
• Dictionary lookups where prefix queries matter
• IP routing / longest prefix match
• When you have many strings sharing common prefixes

When NOT to Use Tries

• Just need exact key lookup → hash map (simpler, less memory)
• Small dictionary → sorted slice + binary search
• Keys aren't strings (integers, structs) → hash map or BST
• Memory is tight → tries use a lot of space for sparse data

Practice Problems

Key Takeaways

• A trie stores one character per edge — paths from root represent prefixes
• Insert, search, and prefix check are all O(m) where m is the key length
• Tries are the only structure that makes prefix queries efficient — hash maps can't do it
• Autocomplete is the killer app: navigate to prefix node, DFS to collect completions
• Tries use more memory than hash maps — 26 pointers per node for English lowercase
• Real-world uses: search autocomplete, spell check, IP routing, DNS