go 75 lines · 9 steps

Building a frequency-ranked autocomplete trie in Go

A prefix tree stores words by character, then walks a subtree to return the top-ranked completions of any prefix.

Explained by highlit
Intermediate trie autocomplete recursion data-structures ranking
1package trie
2 
3import "sort"
4 
5type node struct {
6 children map[rune]*node
7 isWord bool
8 freq int
9}
10 
11type Trie struct {
12 root *node
13}
14 
15func New() *Trie {
16 return &Trie{root: &node{children: make(map[rune]*node)}}
17}
18 
19func (t *Trie) Insert(word string, freq int) {
20 cur := t.root
21 for _, r := range word {
22 next, ok := cur.children[r]
23 if !ok {
24 next = &node{children: make(map[rune]*node)}
25 cur.children[r] = next
26 }
27 cur = next
28 }
29 cur.isWord = true
30 cur.freq = freq
31}
32 
33type suggestion struct {
34 word string
35 freq int
36}
37 
38func (t *Trie) Autocomplete(prefix string, limit int) []string {
39 cur := t.root
40 for _, r := range prefix {
41 next, ok := cur.children[r]
42 if !ok {
43 return nil
44 }
45 cur = next
46 }
47 
48 var found []suggestion
49 var walk func(n *node, path string)
50 walk = func(n *node, path string) {
51 if n.isWord {
52 found = append(found, suggestion{path, n.freq})
53 }
54 for r, child := range n.children {
55 walk(child, path+string(r))
56 }
57 }
58 walk(cur, prefix)
59 
60 sort.Slice(found, func(i, j int) bool {
61 if found[i].freq != found[j].freq {
62 return found[i].freq > found[j].freq
63 }
64 return found[i].word < found[j].word
65 })
66 
67 if limit > len(found) {
68 limit = len(found)
69 }
70 results := make([]string, limit)
71 for i := 0; i < limit; i++ {
72 results[i] = found[i].word
73 }
74 return results
75}
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1A trie shares prefixes across words, so navigating to a prefix is just following the map edges character by character.
  2. 2A recursive closure over a subtree cleanly collects every word beneath a given node.
  3. 3Ranking by frequency then alphabetically gives deterministic, useful autocomplete ordering.

Related explainers

go 
package streaming
 
import (
	"bufio"

Streaming NDJSON logs over HTTP in Go

http-streaming channels select
Advanced 10 steps
javascript 
function evaluate(expression) {
  const tokens = tokenize(expression);
  let pos = 0;
 

Building a recursive descent calculator

parsing recursion operator-precedence
Intermediate 8 steps
go 
package api
 
import (
	"crypto/sha256"

ETag conditional requests in Gin

http-caching etag conditional-requests
Intermediate 6 steps
go 
func (w *Watcher) resetDebounce(d time.Duration) {
	if !w.timer.Stop() {
		select {
		case <-w.timer.C:

Debouncing a stream of events in Go

debounce timers channels
Advanced 7 steps
go 
package logging
 
import (
	"context"

Deduplicating log attributes in Go's slog

decorator-pattern structured-logging immutability
Intermediate 8 steps
go 
package middleware
 
import (
	"net/http"

Per-plan export limits in Gin middleware

middleware rate-limiting authorization
Intermediate 7 steps

Share this explainer

Here's the card — post it anywhere.

Building a frequency-ranked autocomplete trie in Go — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code