Trie (Prefix Tree)

calendarDec 13, 2025 · 9 min read · trie prefix-tree data-structures string-algorithms  ·
Share on: linkedincopy

A Trie (pronounced "try") is a tree-like data structure used to store and retrieve strings efficiently. Each path from root to a node represents a prefix.

Structure

 1type TrieNode struct {
 2    children map[rune]*TrieNode
 3    isEnd    bool  // Marks end of a word
 4}
 5
 6type Trie struct {
 7    root *TrieNode
 8}
 9
10func NewTrie() *Trie {
11    return &Trie{
12        root: &TrieNode{
13            children: make(map[rune]*TrieNode),
14        },
15    }
16}

Visualization

Words stored: "cat", "car", "the", "their"

Core Operations

1. Insert

 1func (t *Trie) Insert(word string) {
 2    node := t.root
 3    
 4    for _, char := range word {
 5        if node.children[char] == nil {
 6            node.children[char] = &TrieNode{
 7                children: make(map[rune]*TrieNode),
 8            }
 9        }
10        node = node.children[char]
11    }
12    
13    node.isEnd = true
14}
15
16// Example
17func main() {
18    trie := NewTrie()
19    trie.Insert("cat")
20    trie.Insert("car")
21    trie.Insert("card")
22}

Time: $O(m)$ where $m$ is word length
Space: $O(m)$

 1func (t *Trie) Search(word string) bool {
 2    node := t.root
 3    
 4    for _, char := range word {
 5        if node.children[char] == nil {
 6            return false
 7        }
 8        node = node.children[char]
 9    }
10    
11    return node.isEnd
12}
13
14// Example
15func main() {
16    trie := NewTrie()
17    trie.Insert("cat")
18    
19    fmt.Println(trie.Search("cat"))  // true
20    fmt.Println(trie.Search("ca"))   // false (not a complete word)
21    fmt.Println(trie.Search("dog"))  // false
22}

Time: $O(m)$
Space: $O(1)$

 1func (t *Trie) StartsWith(prefix string) bool {
 2    node := t.root
 3    
 4    for _, char := range prefix {
 5        if node.children[char] == nil {
 6            return false
 7        }
 8        node = node.children[char]
 9    }
10    
11    return true
12}
13
14// Example
15func main() {
16    trie := NewTrie()
17    trie.Insert("apple")
18    
19    fmt.Println(trie.StartsWith("app"))  // true
20    fmt.Println(trie.StartsWith("appl")) // true
21    fmt.Println(trie.StartsWith("ban"))  // false
22}

Time: $O(m)$
Space: $O(1)$

4. Delete

 1func (t *Trie) Delete(word string) bool {
 2    return t.deleteHelper(t.root, word, 0)
 3}
 4
 5func (t *Trie) deleteHelper(node *TrieNode, word string, index int) bool {
 6    if index == len(word) {
 7        if !node.isEnd {
 8            return false // Word doesn't exist
 9        }
10        
11        node.isEnd = false
12        
13        // Return true if node has no children (can be deleted)
14        return len(node.children) == 0
15    }
16    
17    char := rune(word[index])
18    child := node.children[char]
19    
20    if child == nil {
21        return false // Word doesn't exist
22    }
23    
24    shouldDeleteChild := t.deleteHelper(child, word, index+1)
25    
26    if shouldDeleteChild {
27        delete(node.children, char)
28        // Return true if current node has no children and is not end of another word
29        return len(node.children) == 0 && !node.isEnd
30    }
31    
32    return false
33}

Time: $O(m)$
Space: $O(m)$ for recursion

5. Find All Words with Prefix

 1func (t *Trie) FindWordsWithPrefix(prefix string) []string {
 2    node := t.root
 3    
 4    // Navigate to prefix
 5    for _, char := range prefix {
 6        if node.children[char] == nil {
 7            return []string{}
 8        }
 9        node = node.children[char]
10    }
11    
12    // Collect all words from this point
13    words := []string{}
14    t.collectWords(node, prefix, &words)
15    return words
16}
17
18func (t *Trie) collectWords(node *TrieNode, current string, words *[]string) {
19    if node.isEnd {
20        *words = append(*words, current)
21    }
22    
23    for char, child := range node.children {
24        t.collectWords(child, current+string(char), words)
25    }
26}
27
28// Example
29func main() {
30    trie := NewTrie()
31    words := []string{"cat", "car", "card", "care", "careful", "dog"}
32    for _, word := range words {
33        trie.Insert(word)
34    }
35    
36    fmt.Println(trie.FindWordsWithPrefix("car"))
37    // Output: [car, card, care, careful]
38}

Time: $O(p + n)$ where $p$ is prefix length, $n$ is number of nodes in subtree
Space: $O(n)$

Advanced Operations

Autocomplete

 1func (t *Trie) Autocomplete(prefix string, maxResults int) []string {
 2    node := t.root
 3    
 4    // Navigate to prefix
 5    for _, char := range prefix {
 6        if node.children[char] == nil {
 7            return []string{}
 8        }
 9        node = node.children[char]
10    }
11    
12    // Collect words with limit
13    words := []string{}
14    t.collectWordsLimited(node, prefix, &words, maxResults)
15    return words
16}
17
18func (t *Trie) collectWordsLimited(node *TrieNode, current string, words *[]string, limit int) {
19    if len(*words) >= limit {
20        return
21    }
22    
23    if node.isEnd {
24        *words = append(*words, current)
25    }
26    
27    for char, child := range node.children {
28        if len(*words) >= limit {
29            return
30        }
31        t.collectWordsLimited(child, current+string(char), words, limit)
32    }
33}

Longest Common Prefix

 1func (t *Trie) LongestCommonPrefix() string {
 2    if t.root == nil || len(t.root.children) == 0 {
 3        return ""
 4    }
 5    
 6    prefix := ""
 7    node := t.root
 8    
 9    for len(node.children) == 1 && !node.isEnd {
10        for char, child := range node.children {
11            prefix += string(char)
12            node = child
13        }
14    }
15    
16    return prefix
17}

Word Count

 1func (t *Trie) CountWords() int {
 2    return t.countWordsHelper(t.root)
 3}
 4
 5func (t *Trie) countWordsHelper(node *TrieNode) int {
 6    count := 0
 7    
 8    if node.isEnd {
 9        count = 1
10    }
11    
12    for _, child := range node.children {
13        count += t.countWordsHelper(child)
14    }
15    
16    return count
17}

Complexity Analysis

OperationTimeSpace
Insert$O(m)$$O(m)$
Search$O(m)$$O(1)$
StartsWith$O(m)$$O(1)$
Delete$O(m)$$O(m)$
Find All with Prefix$O(p + n)$$O(n)$

where:

  • $m$ = length of word
  • $p$ = length of prefix
  • $n$ = number of nodes in subtree

Space Complexity: $O(\text{ALPHABET_SIZE} \times N \times M)$ where:

  • ALPHABET_SIZE = character set size
  • N = number of words
  • M = average word length

Optimizations

1. Array-Based Children (for small alphabets)

 1const ALPHABET_SIZE = 26
 2
 3type TrieNodeArray struct {
 4    children [ALPHABET_SIZE]*TrieNodeArray
 5    isEnd    bool
 6}
 7
 8func charToIndex(ch rune) int {
 9    return int(ch - 'a')
10}
11
12func (t *TrieArray) Insert(word string) {
13    node := t.root
14    
15    for _, char := range word {
16        index := charToIndex(char)
17        if node.children[index] == nil {
18            node.children[index] = &TrieNodeArray{}
19        }
20        node = node.children[index]
21    }
22    
23    node.isEnd = true
24}

Advantage: Faster access, $O(1)$ child lookup
Disadvantage: More memory if sparse

2. Compressed Trie (Radix Tree / Patricia Trie)

Store strings on edges instead of single characters.

1type RadixNode struct {
2    children map[string]*RadixNode
3    isEnd    bool
4}

Advantage: Space-efficient for sparse tries
Example: "test" and "testing" share edge "test"

Applications

1. Autocomplete

 1type AutocompleteSystem struct {
 2    trie *Trie
 3}
 4
 5func (a *AutocompleteSystem) AddWord(word string) {
 6    a.trie.Insert(word)
 7}
 8
 9func (a *AutocompleteSystem) GetSuggestions(prefix string, limit int) []string {
10    return a.trie.Autocomplete(prefix, limit)
11}

2. Spell Checker

 1func (t *Trie) SpellCheck(word string) []string {
 2    if t.Search(word) {
 3        return []string{word} // Correct spelling
 4    }
 5    
 6    // Find similar words (simple version: edit distance 1)
 7    suggestions := []string{}
 8    
 9    // Try all possible single-character edits
10    for i := 0; i < len(word); i++ {
11        // Deletion
12        candidate := word[:i] + word[i+1:]
13        if t.Search(candidate) {
14            suggestions = append(suggestions, candidate)
15        }
16        
17        // Substitution
18        for ch := 'a'; ch <= 'z'; ch++ {
19            candidate := word[:i] + string(ch) + word[i+1:]
20            if t.Search(candidate) {
21                suggestions = append(suggestions, candidate)
22            }
23        }
24    }
25    
26    return suggestions
27}

3. IP Routing (Longest Prefix Match)

 1type IPTrie struct {
 2    root *TrieNode
 3}
 4
 5func (ipt *IPTrie) AddRoute(ipPrefix string, nextHop string) {
 6    // Store routing information in trie
 7    // Each bit of IP becomes a path in trie
 8}
 9
10func (ipt *IPTrie) LongestPrefixMatch(ip string) string {
11    // Find longest matching prefix for routing
12    return ""
13}

4. Word Search in Grid

 1func FindWords(board [][]byte, words []string) []string {
 2    // Build trie from words
 3    trie := NewTrie()
 4    for _, word := range words {
 5        trie.Insert(word)
 6    }
 7    
 8    result := []string{}
 9    visited := make([][]bool, len(board))
10    for i := range visited {
11        visited[i] = make([]bool, len(board[0]))
12    }
13    
14    // DFS from each cell
15    for i := 0; i < len(board); i++ {
16        for j := 0; j < len(board[0]); j++ {
17            dfsWordSearch(board, i, j, trie.root, "", &result, visited)
18        }
19    }
20    
21    return result
22}
23
24func dfsWordSearch(board [][]byte, i, j int, node *TrieNode, current string, result *[]string, visited [][]bool) {
25    if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) || visited[i][j] {
26        return
27    }
28    
29    char := rune(board[i][j])
30    if node.children[char] == nil {
31        return
32    }
33    
34    visited[i][j] = true
35    current += string(char)
36    node = node.children[char]
37    
38    if node.isEnd {
39        *result = append(*result, current)
40        node.isEnd = false // Avoid duplicates
41    }
42    
43    // Explore all 4 directions
44    dfsWordSearch(board, i+1, j, node, current, result, visited)
45    dfsWordSearch(board, i-1, j, node, current, result, visited)
46    dfsWordSearch(board, i, j+1, node, current, result, visited)
47    dfsWordSearch(board, i, j-1, node, current, result, visited)
48    
49    visited[i][j] = false // Backtrack
50}

Trie vs. Hash Table

FeatureTrieHash Table
Search$O(m)$$O(1)$ average
Prefix Search$O(p)$$O(n)$ (scan all keys)
Space$O(ALPHABET \times N \times M)$$O(N \times M)$
OrderedYes (lexicographic)No
CollisionNoYes
AutocompleteEfficientInefficient

When to Use Trie

✅ Use when:

  • Prefix-based operations (autocomplete, spell check)
  • Dictionary with many words sharing prefixes
  • IP routing (longest prefix match)
  • Word games (Boggle, Scrabble)
  • T9 predictive text

❌ Don't use when:

  • Simple exact-match lookups (use hash table)
  • Memory is very limited
  • Alphabet size is huge (use compressed trie)
  • No prefix operations needed

Complete Implementation

 1package main
 2
 3import "fmt"
 4
 5type TrieNode struct {
 6    children map[rune]*TrieNode
 7    isEnd    bool
 8    count    int // Number of words passing through this node
 9}
10
11type Trie struct {
12    root *TrieNode
13}
14
15func NewTrie() *Trie {
16    return &Trie{
17        root: &TrieNode{
18            children: make(map[rune]*TrieNode),
19        },
20    }
21}
22
23func (t *Trie) Insert(word string) {
24    node := t.root
25    
26    for _, char := range word {
27        if node.children[char] == nil {
28            node.children[char] = &TrieNode{
29                children: make(map[rune]*TrieNode),
30            }
31        }
32        node = node.children[char]
33        node.count++
34    }
35    
36    node.isEnd = true
37}
38
39func (t *Trie) Search(word string) bool {
40    node := t.root
41    
42    for _, char := range word {
43        if node.children[char] == nil {
44            return false
45        }
46        node = node.children[char]
47    }
48    
49    return node.isEnd
50}
51
52func (t *Trie) StartsWith(prefix string) bool {
53    node := t.root
54    
55    for _, char := range prefix {
56        if node.children[char] == nil {
57            return false
58        }
59        node = node.children[char]
60    }
61    
62    return true
63}
64
65func (t *Trie) CountWordsWithPrefix(prefix string) int {
66    node := t.root
67    
68    for _, char := range prefix {
69        if node.children[char] == nil {
70            return 0
71        }
72        node = node.children[char]
73    }
74    
75    return node.count
76}
77
78func main() {
79    trie := NewTrie()
80    
81    words := []string{"cat", "car", "card", "care", "careful", "dog", "dodge"}
82    for _, word := range words {
83        trie.Insert(word)
84    }
85    
86    fmt.Println("Search 'car':", trie.Search("car"))           // true
87    fmt.Println("Search 'ca':", trie.Search("ca"))             // false
88    fmt.Println("StartsWith 'car':", trie.StartsWith("car"))   // true
89    fmt.Println("Words with prefix 'car':", trie.CountWordsWithPrefix("car")) // 4
90}

Related Snippets

  • Binary Search
    Binary search is an efficient algorithm for finding a target value in a sorted …
  • Binary Tree
    A binary tree is a tree data structure where each node has at most two children, …
  • General Tree
    A tree is a hierarchical data structure consisting of nodes connected by edges, …
  • Heap Data Structure
    A heap is a specialized tree-based data structure that satisfies the heap …
  • Heap Sort
    Heap sort is a comparison-based sorting algorithm that uses a binary heap data …
  • Linked List Operations
    Optimal techniques for common linked list operations using pointer manipulation, …
  • LRU and LFU Cache
    Cache replacement policies determine which items to evict when the cache is …
  • Merge Sort
    Merge sort is a stable, comparison-based sorting algorithm that uses the …
  • Quadtree
    A Quadtree is a tree data structure where each internal node has exactly four …
  • Quick Sort
    Quick sort is an efficient, in-place, comparison-based sorting algorithm that …
  • String Similarity Algorithms
    Algorithms for measuring similarity between strings, used in spell checking, DNA …
  • Terrain & Heightmap Generation
    Procedural terrain generation creates realistic landscapes using mathematical …
  • Wave Function Collapse
    Wave Function Collapse (WFC) is a procedural generation algorithm that creates …