How to Implement a Trie for Efficient Prefix Matching and Autocomplete

A Trie (prefix tree) stores strings by sharing common prefixes, enabling O(L) lookup times for search and autocomplete operations where L is the length of the query.

To implement a Trie for efficient prefix matching and autocomplete, you need a tree-like structure where each node represents a character and paths from the root form words. The labuladong/fucking-algorithm repository references this data structure extensively, pointing to a complete Go implementation that demonstrates insert, search, and prefix-based retrieval operations.

Core Architecture of a Trie

A Trie consists of nodes linked by character edges. Each node tracks whether it terminates a valid word and maintains references to subsequent characters.

Node Structure Each node contains a fixed-size array or hash map for child pointers and a boolean flag. For lowercase English letters, a [26]*Node array provides O(1) access without hashing overhead.

Root Sentinel An empty root node anchors the tree. All words branch from this starting point, allowing the structure to share common prefixes like "de" in "deer" and "deal".

Core Operations

• Insert(word) – Walks character by character, creating missing nodes, then marks the final node with isWord = true. Runs in O(L) time where L is the word length.
• Search(word) – Traverses the tree and returns true only if the path exists and the terminal node has isWord set.
• StartsWith(prefix) – Identical to search but ignores the isWord flag, confirming the prefix exists in O(P) time.
• Autocomplete(prefix, limit) – Locates the prefix node, then performs DFS/BFS to collect words until reaching the limit.

Why Tries Excel at Prefix Problems

Deterministic Lookup Time Unlike hash tables that degrade with collisions or trees requiring logarithmic comparisons, a Trie guarantees O(L) access regardless of the dictionary size. Each character advances exactly one level.

Memory Sharing Common prefixes are stored once. For dictionaries with shared roots (e.g., "interview", "internet", "internal"), this compression significantly reduces redundancy compared to storing full strings in a list.

Fast Enumeration Finding all words with a given prefix requires only a subtree traversal starting from the prefix node. This avoids scanning the entire dataset, making autocomplete features responsive even with large lexicons.

Go Implementation

The following implementation mirrors the approach documented in the labuladong/fucking-algorithm repository. It uses a fixed [26]*Node array optimized for lowercase English letters.

The Node Structure

package trie

type Node struct {
    children [26]*Node // fixed-size array for 'a'-'z'
    isWord   bool
}

type Trie struct {
    root *Node
}

func New() *Trie { 
    return &Trie{root: &Node{}} 
}

The children array provides index-based access via char - 'a', eliminating map overhead for constrained alphabets.

Insert, Search, and StartsWith

func (t *Trie) Insert(word string) {
    cur := t.root
    for _, r := range word {
        idx := int(r - 'a')
        if cur.children[idx] == nil {
            cur.children[idx] = &Node{}
        }
        cur = cur.children[idx]
    }
    cur.isWord = true
}

func (t *Trie) Search(word string) bool {
    node := t.findNode(word)
    return node != nil && node.isWord
}

func (t *Trie) StartsWith(prefix string) bool {
    return t.findNode(prefix) != nil
}

func (t *Trie) findNode(s string) *Node {
    cur := t.root
    for _, r := range s {
        idx := int(r - 'a')
        if cur.children[idx] == nil {
            return nil
        }
        cur = cur.children[idx]
    }
    return cur
}

The findNode helper centralizes traversal logic, returning nil if any character is missing or the terminal node when the path exists.

Autocomplete Implementation

func (t *Trie) Autocomplete(prefix string, limit int) []string {
    start := t.findNode(prefix)
    if start == nil {
        return nil
    }
    
    var res []string
    var dfs func(*Node, []rune)
    
    dfs = func(n *Node, path []rune) {
        if limit > 0 && len(res) >= limit {
            return
        }
        if n.isWord {
            res = append(res, string(append([]rune(prefix), path...)))
        }
        for i, child := range n.children {
            if child != nil {
                dfs(child, append(path, rune('a'+i)))
            }
        }
    }
    
    dfs(start, []rune{})
    return res
}

This method performs a depth-first search from the prefix node, accumulating characters until it discovers complete words or hits the user-defined limit.

Complete Usage Example

package main

import (
    "fmt"
    "github.com/yourmodule/trie"
)

func main() {
    tr := trie.New()
    words := []string{"dog", "deer", "deal", "cat"}
    
    for _, w := range words {
        tr.Insert(w)
    }

    fmt.Println(tr.Search("deer"))      // true
    fmt.Println(tr.Search("dee"))       // false (prefix only)
    fmt.Println(tr.StartsWith("de"))    // true
    
    // Retrieve up to 5 completions for "de"
    fmt.Println(tr.Autocomplete("de", 5))
    // Output: [deer deal]
}

Source Files in labuladong/fucking-algorithm

While the repository does not contain the full source file for the Trie implementation directly, it maintains comprehensive references in several Markdown files:

• README.md – Lists the Trie section under "Trie/字典树/前缀树代码实现" and links to the detailed implementation at labuladong.online/algo/data-structure/trie-implement/.
• 算法思维系列/回溯算法详解修订版.md – References the same external Trie URL for readers studying backtracking applications.
• 数据结构系列/二叉树总结.md – Contains the external link for data structure comparisons.
• 数据结构系列/BST2.md – Points to the Trie implementation page for binary search tree alternatives.

These files serve as the repository's index, directing developers to the author's complete Go implementation, visualizations, and practice problems.

Summary

• A Trie stores characters in a tree structure where each level represents one character, enabling O(L) insert, search, and prefix checks.
• Use a fixed-size array ([26]*Node) for limited alphabets to maximize cache locality and minimize overhead, or a hash map for Unicode support.
• The Autocomplete method locates the prefix node then performs DFS to enumerate completions efficiently without scanning the entire dataset.
• The labuladong/fucking-algorithm repository indexes this implementation in README.md and related Markdown files, linking to the full code at labuladong.online.

Frequently Asked Questions

What is the time complexity of Trie operations?

Insertion, exact search, and prefix checks all run in O(L) time where L is the length of the input string. Autocomplete runs in O(P + k) where P is the prefix length and k is the number of nodes visited during the traversal to collect results. These complexities remain constant regardless of how many words are stored in the Trie.

How does a Trie compare to a hash table for string storage?

A Trie shares common prefixes to reduce memory redundancy for similar words, whereas a hash table stores each complete string separately. While hash tables offer O(1) average-case lookups, they cannot efficiently enumerate all keys with a given prefix without scanning the entire table. Tries provide deterministic O(L) lookups and native support for prefix operations.

Can I implement a Trie for Unicode or large alphabets?

Yes, but you should replace the [26]*Node array with a hash map (map[rune]*Node or map[byte]*Node). This trades constant-time index access for O(1) map lookups and reduces memory waste when the alphabet is sparse, though it may decrease cache locality compared to the fixed-array approach.

Where can I find the original implementation by labuladong?

The labuladong/fucking-algorithm repository references the full implementation in README.md and several data structure guides including 数据结构系列/二叉树总结.md and 算法思维系列/回溯算法详解修订版.md. These files link to the complete tutorial and source code hosted at labuladong.online/algo/data-structure/trie-implement/.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}