Tries

A tree of characters where words sharing a prefix share a path: fast prefix search, autocomplete, and wildcard matching.

The structure#

Insert go, gopher, goal and do. Each node is labelled with the prefix it spells, and ✓ marks a node where a word ends:

Drawing diagram…

Each node holds its children and a flag saying whether a word ends there. The flag matters: the path g-o-p exists, but "gop" was never inserted.

type Trie struct {
	children [26]*Trie // one slot per lowercase letter
	end      bool
}

Insert#

Walk from the root, one character at a time; create missing children; mark the last node as an end.

Insert goal into a trie that already holds go:

char	child exists?	action
g	yes	move
o	yes	move
a	no	create, move
l	no	create, move
(end)		`end = true`

Only two new nodes, because "go" was shared.

Run the trace

The program counts nodes as it goes, so you can see how much the shared prefixes save:

trie_insert_trace.go

package main
 
import "fmt"
 
type Trie struct {
	children [26]*Trie
	end      bool
}
 
var nodes = 1 // the root
 
func (t *Trie) Insert(w string) {
	node := t
	fmt.Printf("insert %-7s", w)
	for i := 0; i < len(w); i++ {
		c := w[i] - 'a'
		if node.children[c] == nil {
			node.children[c] = &Trie{}
			nodes++
			fmt.Printf(" +%c", w[i]) // created
		} else {
			fmt.Printf("  %c", w[i]) // shared
		}
		node = node.children[c]
	}
	node.end = true
	fmt.Printf("   (total nodes %d)\n", nodes)
}
 
func main() {
	t := &Trie{}
	letters := 0
	for _, w := range []string{"go", "gopher", "goal", "do", "dog"} {
		t.Insert(w)
		letters += len(w)
	}
	fmt.Println("letters inserted:", letters, " nodes besides the root:", nodes-1)
}

Output

insert go      +g +o   (total nodes 3)
insert gopher   g  o +p +h +e +r   (total nodes 7)
insert goal     g  o +a +l   (total nodes 9)
insert do      +d +o   (total nodes 11)
insert dog      d  o +g   (total nodes 12)
letters inserted: 17  nodes besides the root: 11

+ marks a newly created node. gopher, goal and dog all walk through nodes that already exist, so 17 letters need only 11 nodes. In a real dictionary with thousands of words, most nodes are shared.

Search and prefix search#

Both walk the same path; they differ only at the end:

Query	Walk succeeds and…	Result
`Search("go")`	final node has `end = true`	true
`Search("gop")`	final node has `end = false`	false
`StartsWith("gop")`	the path exists	true
`StartsWith("gx")`	the walk hits a nil child	false

Try it

trie_search.go

package main
 
import "fmt"
 
type Trie struct {
	children [26]*Trie
	end      bool
}
 
func (t *Trie) Insert(w string) {
	node := t
	for i := 0; i < len(w); i++ {
		c := w[i] - 'a'
		if node.children[c] == nil {
			node.children[c] = &Trie{}
		}
		node = node.children[c]
	}
	node.end = true
}
 
// walk returns the node at the end of prefix p, or nil if the path breaks.
func (t *Trie) walk(p string) *Trie {
	node := t
	for i := 0; i < len(p) && node != nil; i++ {
		node = node.children[p[i]-'a']
	}
	return node
}
 
func (t *Trie) Search(w string) bool     { n := t.walk(w); return n != nil && n.end }
func (t *Trie) StartsWith(p string) bool { return t.walk(p) != nil }
 
func main() {
	t := &Trie{}
	for _, w := range []string{"go", "gopher", "goal", "do"} {
		t.Insert(w)
	}
	for _, q := range []string{"go", "gop", "gopher", "gx", "d"} {
		fmt.Printf("%-7s Search=%-5v StartsWith=%v\n", q, t.Search(q), t.StartsWith(q))
	}
}

Output

go      Search=true  StartsWith=true
gop     Search=false StartsWith=true
gopher  Search=true  StartsWith=true
gx      Search=false StartsWith=false
d       Search=false StartsWith=true

Autocomplete#

Walk to the prefix's node, then DFS beneath it, collecting every node marked end. Visiting children in alphabetical order (index 0 to 25) returns suggestions already sorted.

Run the trace

The DFS prints the path it is on. Children are visited from a to z, so the words come out sorted without calling sort:

autocomplete_trace.go

package main
 
import "fmt"
 
type Trie struct {
	children [26]*Trie
	end      bool
}
 
func (t *Trie) Insert(w string) {
	node := t
	for i := 0; i < len(w); i++ {
		c := w[i] - 'a'
		if node.children[c] == nil {
			node.children[c] = &Trie{}
		}
		node = node.children[c]
	}
	node.end = true
}
 
func (t *Trie) Complete(prefix string) []string {
	node := t
	for i := 0; i < len(prefix); i++ {
		if node = node.children[prefix[i]-'a']; node == nil {
			return nil
		}
	}
	var out []string
	var dfs func(n *Trie, path []byte)
	dfs = func(n *Trie, path []byte) {
		if n.end {
			fmt.Println("  word ends at", string(path))
			out = append(out, string(path))
		}
		for c, child := range n.children {
			if child != nil {
				dfs(child, append(path, byte('a'+c)))
			}
		}
	}
	dfs(node, []byte(prefix))
	return out
}
 
func main() {
	t := &Trie{}
	for _, w := range []string{"gopher", "go", "golang", "goal", "do", "gone"} {
		t.Insert(w)
	}
	fmt.Println("complete \"go\":")
	fmt.Println(t.Complete("go"))
	fmt.Println("complete \"gol\":")
	fmt.Println(t.Complete("gol"))
	fmt.Println("complete \"x\":")
	fmt.Println(t.Complete("x"))
}

Output

complete "go":
  word ends at go
  word ends at goal
  word ends at golang
  word ends at gone
  word ends at gopher
[go goal golang gone gopher]
complete "gol":
  word ends at golang
[golang]
complete "x":
[]

Wildcards#

For "Add and Search Words", a . matches any letter. At a ., recursively try every non-nil child; at a normal letter, follow one edge.

Run the trace

wildcard_trace.go

package main
 
import (
	"fmt"
	"strings"
)
 
type Trie struct {
	children [26]*Trie
	end      bool
}
 
func (t *Trie) Insert(w string) {
	node := t
	for i := 0; i < len(w); i++ {
		c := w[i] - 'a'
		if node.children[c] == nil {
			node.children[c] = &Trie{}
		}
		node = node.children[c]
	}
	node.end = true
}
 
func (t *Trie) Match(pattern string) bool {
	var dfs func(n *Trie, i int, path string) bool
	dfs = func(n *Trie, i int, path string) bool {
		if i == len(pattern) {
			fmt.Printf("%sreached %q: end=%v\n", strings.Repeat("  ", i), path, n.end)
			return n.end
		}
		if pattern[i] != '.' {
			child := n.children[pattern[i]-'a']
			return child != nil && dfs(child, i+1, path+pattern[i:i+1])
		}
		for c, child := range n.children { // '.' tries every child
			if child != nil && dfs(child, i+1, path+string(rune('a'+c))) {
				return true
			}
		}
		return false
	}
	return dfs(t, 0, "")
}
 
func main() {
	t := &Trie{}
	for _, w := range []string{"bad", "dad", "mad", "bat"} {
		t.Insert(w)
	}
	fmt.Println("pattern .at")
	fmt.Println("result:", t.Match(".at"))
	fmt.Println("pattern b..")
	fmt.Println("result:", t.Match("b.."))
}

Output

pattern .at
      reached "bat": end=true
result: true
pattern b..
      reached "bad": end=true
result: true

For .at, the . tries b, d and m, but only b continues with an a and then a t. Paths that break early, such as d then a then no t, print nothing because they never reach the end of the pattern.

Choosing the children type#

Children	Speed	Memory	Characters
`[26]*Trie`	fastest (direct index)	26 pointers per node, even if empty	lowercase a–z
`map[rune]*Trie`	slower (hashing)	only what's used	any Unicode

Try it: any language

With map[rune]*Node children, the same trie handles accents, other scripts and emoji. range over a string yields runes, not bytes:

unicode_trie.go

package main
 
import (
	"fmt"
	"slices"
)
 
type Node struct {
	children map[rune]*Node
	end      bool
}
 
func newNode() *Node { return &Node{children: map[rune]*Node{}} }
 
func (t *Node) Insert(w string) {
	node := t
	for _, r := range w {
		if node.children[r] == nil {
			node.children[r] = newNode()
		}
		node = node.children[r]
	}
	node.end = true
}
 
func (t *Node) Complete(prefix string) []string {
	node := t
	for _, r := range prefix {
		if node = node.children[r]; node == nil {
			return nil
		}
	}
	var out []string
	var dfs func(n *Node, path string)
	dfs = func(n *Node, path string) {
		if n.end {
			out = append(out, path)
		}
		for r, child := range n.children {
			dfs(child, path+string(r))
		}
	}
	dfs(node, prefix)
	slices.Sort(out) // map order is random, so sort the result
	return out
}
 
func main() {
	t := newNode()
	for _, w := range []string{"café", "cafetería", "caña", "東京", "東北"} {
		t.Insert(w)
	}
	fmt.Println(t.Complete("caf"))
	fmt.Println(t.Complete("東"))
}

Output

[cafetería café]
[東京 東北]

The full program#

trie.go

package main
 
import (
	"fmt"
	"strings"
)
 
type Trie struct {
	children [26]*Trie
	end      bool
}
 
func (t *Trie) Insert(word string) {
	node := t
	for i := 0; i < len(word); i++ {
		c := word[i] - 'a'
		if node.children[c] == nil {
			node.children[c] = &Trie{}
		}
		node = node.children[c]
	}
	node.end = true
}
 
// walk follows s from t and returns the node it ends at, or nil.
func (t *Trie) walk(s string) *Trie {
	node := t
	for i := 0; i < len(s) && node != nil; i++ {
		node = node.children[s[i]-'a']
	}
	return node
}
 
func (t *Trie) Search(word string) bool {
	n := t.walk(word)
	return n != nil && n.end
}
 
func (t *Trie) StartsWith(prefix string) bool { return t.walk(prefix) != nil }
 
// Complete returns up to limit words starting with prefix, in alphabetical order.
func (t *Trie) Complete(prefix string, limit int) []string {
	var out []string
	var buf []byte
	var dfs func(n *Trie)
	dfs = func(n *Trie) {
		if len(out) == limit {
			return
		}
		if n.end {
			out = append(out, prefix+string(buf))
		}
		for c, child := range n.children {
			if child != nil {
				buf = append(buf, byte('a'+c))
				dfs(child)
				buf = buf[:len(buf)-1]
			}
		}
	}
	if start := t.walk(prefix); start != nil {
		dfs(start)
	}
	return out
}
 
// Match supports '.' as a wildcard for any single letter.
func (t *Trie) Match(pattern string) bool {
	if pattern == "" {
		return t.end
	}
	if pattern[0] == '.' {
		for _, child := range t.children {
			if child != nil && child.Match(pattern[1:]) {
				return true
			}
		}
		return false
	}
	child := t.children[pattern[0]-'a']
	return child != nil && child.Match(pattern[1:])
}
 
func main() {
	t := &Trie{}
	for _, w := range strings.Fields("go gopher goal do dog golang") {
		t.Insert(w)
	}
	fmt.Println(t.Search("go"), t.Search("gop"), t.StartsWith("gop"), t.StartsWith("gx"))
	fmt.Println(t.Complete("go", 10))
	fmt.Println(t.Complete("go", 2))
	fmt.Println(t.Match("d.g"), t.Match("g..l"), t.Match("...."), t.Match("x.."))
}

Output

true false true false
[go goal golang gopher]
[go goal]
true true true false

"...." matches goal, the only 4-letter word stored.

Complexity#

With L = word length and N = number of stored words:

Operation	Time	Space
insert	O(L)	up to L new nodes
search / prefix check	O(L)	O(1)
autocomplete k results	O(L + nodes visited)	O(depth)
wildcard match	O(L) without dots; up to O(26^dots · L)	O(L) recursion
whole trie		O(total characters × alphabet) worst case

Recognizing the pattern#

"Prefix", "starts with", "autocomplete", "dictionary of words" combined with many queries, or searching many words in a grid at once, all point to a trie. For a single lookup, a map of whole words is simpler.

Summary#

A trie stores words as paths of characters; shared prefixes share nodes.
Every node needs an end flag; prefixes are not words.
Insert, search and prefix checks cost O(word length).
DFS under a prefix node gives sorted autocomplete; branching on . gives wildcards.
Use [26]*Trie for a–z, map[rune]*Trie for anything else.

The structure#

Insert#

Run the trace

Search and prefix search#

Try it

Autocomplete#

Run the trace

Wildcards#

Run the trace

Choosing the children type#

Try it: any language

The full program#

Complexity#

Recognizing the pattern#

Summary#

Check your understanding

Practice in Go