# How to Implement a Trie for Efficient Prefix Matching and Autocomplete

> Implement a Trie for lightning-fast prefix matching and autocomplete. Discover O(L) lookup times for efficient string operations and boost your application's performance.

- Repository: [DonglaiFu/fucking-algorithm](https://github.com/labuladong/fucking-algorithm)
- Tags: how-to-guide
- Published: 2026-02-25

---

**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

```go
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

```go
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

```go
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

```go
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`](https://github.com/labuladong/fucking-algorithm/blob/main/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`](https://github.com/labuladong/fucking-algorithm/blob/main/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`](https://github.com/labuladong/fucking-algorithm/blob/main/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/`.