Data Structures

Trie

A trie stores words one letter per node, so everything sharing a prefix shares a path. It is the structure behind autocomplete and prefix search.

The shape

Prefix tree

One node per letter, so words that start the same share a path.

Insert: walk the word, adding a child node for each letter.
Search: walk the same path, then check the terminal flag at the end.
Prefix: walk the prefix and take everything hanging below it.

letters you typed still reachable ends a word

Type a letter, or click one below, and walk the tree one step at a time. Backspace goes back. The panel on the right is what an autocomplete would be showing you.

Purpose

Store words so anything starting with a given prefix comes back quickly.

Input

Words inserted one at a time, as string.

Output

Whether a word is stored, and whether any stored word starts with a prefix.

Constraints

Each node holds a map[rune]*Node, so memory grows with the distinct letters at each level.
A node needs a terminal flag, since a stored word can be the start of a longer one.
Keys are walked rune by rune, so any UTF-8 text works.

How a trie works

A trie stores words one letter per node, so words that start the same way share a path.

Walk c, then a, then r, and you have spelled car. Everything below a node begins with the letters you walked to reach it, which is what puts a trie behind autocomplete and prefix search.

\text{nodes}(w) = |w| + 1

A word of length |w| hangs one node per letter below the root.

What a trie keeps track of

Name	Type	What it is for
Node	struct	One letter in the tree.
Children	map[rune]*Node	The letters allowed to follow this one.
Terminal	bool	Marks a letter that finishes a stored word.
Root	*Node	The empty node every word hangs below.
walk	func(string) *Node	Follows a string letter by letter and reports where it lands.

Walk through it

1 Start with an empty root

The root holds no letter of its own. It is the place every word starts from.

type Node struct {
    Children map[rune]*Node
    Terminal bool
}

root := &Node{Children: map[rune]*Node{}}

2 Add one letter at a time

Ranging a string gives runes, so an accent or an emoji still stores as one node.

n := t.Root
for _, letter := range word {
    next, ok := n.Children[letter]
    if !ok {
        next = NewNode()
        n.Children[letter] = next
    }
    n = next
}

3 Mark where the word ends

The flag is what separates a stored word from letters you merely passed through.

n.Terminal = true

4 Follow a string to see where it lands

The same loop as inserting, minus the creating. A missing letter means nothing stored starts this way.

func (t *Trie) walk(s string) *Node {
    n := t.Root
    for _, letter := range s {
        next, ok := n.Children[letter]
        if !ok {
            return nil
        }
        n = next
    }
    return n
}

5 Separate a stored word from a prefix

Both walk the same path. Landing somewhere answers the prefix; the flag answers the word.

func (t *Trie) Contains(word string) bool {
    n := t.walk(word)
    return n != nil && n.Terminal
}

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

6 Collect everything below a node

Walk to the prefix, visit every node under it, keep the words. Map order is random, so sort.

var collect func(n *Node, word string)
collect = func(n *Node, word string) {
    if n.Terminal {
        found = append(found, word)
    }
    for letter, child := range n.Children {
        collect(child, word+string(letter))
    }
}

The whole program

Store four words, then ask the tree three different questions about them.

package main

import (
    "fmt"
    "slices"
)

// Node is one letter in the tree. Children holds the letters allowed to
// follow it, and Terminal marks a letter that finishes a stored word.
type Node struct {
    Children map[rune]*Node
    Terminal bool
}

func NewNode() *Node {
    return &Node{Children: map[rune]*Node{}}
}

type Trie struct {
    Root *Node
}

func NewTrie() *Trie {
    return &Trie{Root: NewNode()}
}

// Insert walks the word one letter at a time, creating any node missing
// along the way, and marks the last one as the end of a word.
func (t *Trie) Insert(word string) {
    n := t.Root
    for _, letter := range word {
        next, ok := n.Children[letter]
        if !ok {
            next = NewNode()
            n.Children[letter] = next
        }
        n = next
    }
    n.Terminal = true
}

// walk follows s from the root and returns the node it lands on, or nil
// if a letter is missing.
func (t *Trie) walk(s string) *Node {
    n := t.Root
    for _, letter := range s {
        next, ok := n.Children[letter]
        if !ok {
            return nil
        }
        n = next
    }
    return n
}

// Contains reports whether word was stored, rather than merely passed through.
func (t *Trie) Contains(word string) bool {
    n := t.walk(word)
    return n != nil && n.Terminal
}

// HasPrefix reports whether any stored word starts with prefix.
func (t *Trie) HasPrefix(prefix string) bool {
    return t.walk(prefix) != nil
}

// WithPrefix collects every stored word starting with prefix.
func (t *Trie) WithPrefix(prefix string) []string {
    start := t.walk(prefix)
    if start == nil {
        return nil
    }

    var found []string
    var collect func(n *Node, word string)
    collect = func(n *Node, word string) {
        if n.Terminal {
            found = append(found, word)
        }
        for letter, child := range n.Children {
            collect(child, word+string(letter))
        }
    }
    collect(start, prefix)

    slices.Sort(found)
    return found
}

func main() {
    t := NewTrie()
    for _, word := range []string{"car", "cart", "cat", "dog"} {
        t.Insert(word)
    }

    fmt.Println(t.Contains("car"))
    fmt.Println(t.Contains("ca"))
    fmt.Println(t.HasPrefix("ca"))
    fmt.Println(t.WithPrefix("ca"))
    fmt.Println(t.WithPrefix("do"))
    fmt.Println(t.WithPrefix("z"))
}

Terminal

$ go run main.go
true
false
true
[car cart cat]
[dog]
[]

Maps The map[rune]*Node holding each node's letters.Runes Why ranging a string gives characters, not bytes.Graph The same idea of nodes and links, without the tree shape.strings HasPrefix and the flat-search alternative.

Previous Set Next Topic Linked List