Tries and Prefix Trees

Updated

October 31, 2026

Tries and Prefix Trees

A Trie (derived from “retrieval”), also known as a prefix tree, is a specialized tree structure where each edge represents a character of a string key. All descendants of a node share a common string prefix. In Go, the boring default for string lookup is map[string]T, but a Trie shines when you need to match prefixes, validate autocomplete options, or perform IP routing lookups in \(O(L)\) time where \(L\) is the string length, completely independent of how many millions of keys exist.

Mental model

Unlike a binary tree where nodes store whole strings, Trie nodes store transition characters. Shared prefixes share identical parent paths:

                  (Root)
                 /      \
               "c"      "t"
               /          \
             "a"          "e"
            /   \           \
          "r"   "t"         "a"
           |     |           |
        (cart) (cat)       (tea)

Keys: "cart", "cat", "tea"
Searching for "car": Follow root \(\to\) 'c' \(\to\) 'a' \(\to\) 'r'. It exists as a prefix, but whether it is a complete word depends on the boolean flag isTerminal.
Autocomplete: Walk down to the node matching the prefix (e.g. 'c' \(\to\) 'a'), then gather all terminal descendants ("cart", "cat").

Search and insertion cost \(O(L)\) operations where \(L\) is the length of the word, which is ideal for desk SKU catalogs with hundreds of thousands of items.

Worked examples

Case 1: Desk SKU and Tag Autocomplete Trie

Save as trie_desk.go. Implement a generic Trie capable of storing desk SKU metadata and providing prefix autocompletion.

// trie_desk.go
package main

import (
    "fmt"
)

type TrieNode[T any] struct {
    children   map[rune]*TrieNode[T]
    isTerminal bool
    value      T
}

func newTrieNode[T any]() *TrieNode[T] {
    return &TrieNode[T]{
        children: make(map[rune]*TrieNode[T]),
    }
}

type Trie[T any] struct {
    root *TrieNode[T]
    size int
}

func NewTrie[T any]() *Trie[T] {
    return &Trie[T]{root: newTrieNode[T]()}
}

func (t *Trie[T]) Insert(key string, val T) {
    curr := t.root
    for _, ch := range key {
        if _, exists := curr.children[ch]; !exists {
            curr.children[ch] = newTrieNode[T]()
        }
        curr = curr.children[ch]
    }
    if !curr.isTerminal {
        t.size++
    }
    curr.isTerminal = true
    curr.value = val
}

func (t *Trie[T]) Search(key string) (T, bool) {
    curr := t.root
    for _, ch := range key {
        next, exists := curr.children[ch]
        if !exists {
            var zero T
            return zero, false
        }
        curr = next
    }
    if curr.isTerminal {
        return curr.value, true
    }
    var zero T
    return zero, false
}

func (t *Trie[T]) StartsWith(prefix string) bool {
    curr := t.root
    for _, ch := range prefix {
        next, exists := curr.children[ch]
        if !exists {
            return false
        }
        curr = next
    }
    return true
}

func (t *Trie[T]) AutoComplete(prefix string) []string {
    curr := t.root
    for _, ch := range prefix {
        next, exists := curr.children[ch]
        if !exists {
            return nil
        }
        curr = next
    }

    var results []string
    collectWords(curr, prefix, &results)
    return results
}

func collectWords[T any](node *TrieNode[T], current string, results *[]string) {
    if node.isTerminal {
        *results = append(*results, current)
    }
    for ch, child := range node.children {
        collectWords(child, current+string(ch), results)
    }
}

func main() {
    catalog := NewTrie[string]()

    catalog.Insert("DESK-CHAIR", "Ergonomic Mesh Chair")
    catalog.Insert("DESK-LAMP", "LED Adjustable Lamp")
    catalog.Insert("DESK-MAT", "Leather Desk Pad")
    catalog.Insert("DESK-DRAWER", "Under-desk organizer")
    catalog.Insert("DISH-TOWEL", "Barista cleanup towel")

    // Exact search
    sku := "DESK-LAMP"
    if desc, found := catalog.Search(sku); found {
        fmt.Printf("Exact SKU lookup [%s]: %s\n", sku, desc)
    }

    // Prefix check
    pfx := "DESK-"
    fmt.Printf("Any items starting with '%s'? %t\n", pfx, catalog.StartsWith(pfx))

    // Autocomplete recommendations
    suggestions := catalog.AutoComplete("DESK-")
    fmt.Println("\nAutocomplete options for 'DESK-':")
    for _, s := range suggestions {
        desc, _ := catalog.Search(s)
        fmt.Printf("  • %s (%s)\n", s, desc)
    }
}

Run:

go run trie_desk.go

Output:

Exact SKU lookup [DESK-LAMP]: LED Adjustable Lamp
Any items starting with 'DESK-'? true

Autocomplete options for 'DESK-':
  • DESK-CHAIR (Ergonomic Mesh Chair)
  • DESK-LAMP (LED Adjustable Lamp)
  • DESK-MAT (Leather Desk Pad)
  • DESK-DRAWER (Under-desk organizer)

The trap

A common temptation in textbook Trie implementations is using a fixed ASCII array [26]*TrieNode for child pointers. While this avoids map allocations, it panics on uppercase letters, digits, dashes, and UTF-8 characters (ch - 'a' < 0). In Go, strings are UTF-8 by default; using map[rune]*TrieNode safely handles spaces, punctuation, dashes, and non-English characters without buffer overruns.

// bad_ascii_trie.go
package main

import "fmt"

type BadNode struct {
    children [26]*BadNode // TRAP: Only supports lowercase a-z
}

func badInsert(root *BadNode, word string) {
    curr := root
    for _, ch := range word {
        // If word contains '-' or '0'..'9', index goes out of range!
        idx := ch - 'a'
        if idx < 0 || idx >= 26 {
            fmt.Printf("PANIC PREVENTED: rune '%c' is invalid for [26] array!\n", ch)
            return
        }
        if curr.children[idx] == nil {
            curr.children[idx] = &BadNode{}
        }
        curr = curr.children[idx]
    }
}

func main() {
    root := &BadNode{}
    badInsert(root, "DESK-101")
}

Run:

go run bad_ascii_trie.go

Output:

PANIC PREVENTED: rune 'D' is invalid for [26] array!

The boring rule

If you only look up exact keys, use Go’s built-in map[string]V. A hash map is faster and uses less memory than a Trie for exact matches.
Use a Trie when the requirements demand prefix queries: StartsWith, auto-complete, longest-prefix routing, or spell checking.
Use map[rune]*TrieNode in Go to safely handle Unicode runes and symbols.
If memory is tight and paths have long unbranching chains, consider a Radix Tree (compact Trie) where common non-branching edges are merged into single strings.

Try this

Add a Delete(key string) bool method to Trie that removes the terminal marker and prunes child nodes that have no other descendants.
Build an order tag filter where user input "veg" automatically expands to both "vegan" and "vegetarian".