Tries

You type su into a search box and suggestions appear before you finish the word: sun, sum, summer. The app holds a dictionary of thousands of words and answers on every keystroke. Scanning the whole list each time works for a small list and gets slower as the list grows.

Look at the words themselves. Thousands of them start with s. Hundreds start with su. If the words were filed so that everything starting with su sat in one place, a suggestion would be two steps away: go to s, then to u, and read off what is there. That filing system is a trie.

#The idea: one letter per step

A trie (usually pronounced "try", from retrieval) is a tree where each edge is a letter. The path from the root to any node spells out a prefix. Words that share a beginning share the same path, so the prefix su is stored once, however many words start with it.

Each node holds two things:

• children: a map from a letter to the next node, one entry for each letter that can follow this prefix;
• isWord: a flag that says whether a whole word ends here.

The flag matters because a word can be a prefix of another word. Both so and sort pass through the node for so. Only the flag tells you that so is a word on its own and sor is not.

#Building and searching a trie

To insert a word, start at the root and take one letter at a time. If a child for that letter exists, step into it. If not, create it. After the last letter, set the flag.

To search, walk the same way. If a letter has no child, stop: nothing stored starts with that prefix. If you reach the end of the input, you have the node for that prefix. For "is this a word?", check its flag. For "does any word start with this?", reaching the node is enough. For autocomplete, collect every flagged node below it.

Watch five words go in, then three questions. Each circle shows the letter on the edge that leads into it. Green nodes have the flag set, with the word they complete written below.

insert(word):  node = root  for each letter: go to (or create) that child  mark node as the end of a word find(prefix):  node = root  for each letter: go to that child, or stop if missing  return node

#The code

A map of children works for any alphabet, including capital letters, digits and accented characters.

class TrieNode {
  constructor() {
    this.children = new Map(); // letter -> TrieNode
    this.isWord = false;       // does a word end here?
  }
}
 
class Trie {
  constructor() { this.root = new TrieNode(); }
 
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch);
    }
    node.isWord = true; // mark the end of the word
  }
 
  // Follow prefix letter by letter. null if the path breaks.
  find(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      node = node.children.get(ch);
      if (node === undefined) return null;
    }
    return node;
  }
 
  has(word) {
    const node = this.find(word);
    return node !== null && node.isWord;
  }
 
  startsWith(prefix) { return this.find(prefix) !== null; }
}

class TrieNode:
    def __init__(self):
        self.children = {}    # letter -> TrieNode
        self.is_word = False  # does a word end here?
 
class Trie:
    def __init__(self):
        self.root = TrieNode()
 
    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True  # mark the end of the word
 
    # Follow prefix letter by letter. None if the path breaks.
    def find(self, prefix):
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node
 
    def has(self, word):
        node = self.find(word)
        return node is not None and node.is_word
 
    def starts_with(self, prefix):
        return self.find(prefix) is not None

Autocomplete is find followed by a preorder traversal of the subtree, building each word as it goes down:

// Every stored word that begins with prefix.
function complete(trie, prefix) {
  const out = [];
  const start = trie.find(prefix);
  if (start === null) return out;
  const walk = (node, word) => {
    if (node.isWord) out.push(word);
    for (const [ch, child] of node.children) walk(child, word + ch);
  };
  walk(start, prefix);
  return out;
}
 
const trie = new Trie();
for (const w of ["so", "sort", "sun", "sum", "sky"]) trie.insert(w);
complete(trie, "su"); // ["sun", "sum"]
trie.has("sor");      // false
trie.startsWith("sor"); // true

# Every stored word that begins with prefix.
def complete(trie, prefix):
    out = []
    start = trie.find(prefix)
    if start is None:
        return out
 
    def walk(node, word):
        if node.is_word:
            out.append(word)
        for ch, child in node.children.items():
            walk(child, word + ch)
 
    walk(start, prefix)
    return out
 
trie = Trie()
for w in ["so", "sort", "sun", "sum", "sky"]:
    trie.insert(w)
complete(trie, "su")      # ['sun', 'sum']
trie.has("sor")           # False
trie.starts_with("sor")   # True

#Cost

Every operation walks one node per letter of its input. If the word has length L, insert, has and startsWith each take O(L) steps, whether the trie holds 5 words or 5 million. Autocomplete adds the size of the subtree it reads, which is the price of listing the answers.

Memory is at most one node per letter inserted, and less when words share prefixes. Each node carries a map, though, so a trie usually uses more memory than a plain list of the same words.

If you only ever ask "is this exact word stored?", a hash set from Hash Tables is simpler and smaller. Reach for a trie when the questions are about prefixes. A sorted array with binary search can also find the range of words with a given prefix, which is a good choice when the word list never changes.

#Common mistakes

#Check yourself

#What to practise next

Tries, heaps and search trees all lean on one thing: a short tree. Balanced Trees shows how search trees keep themselves short, whatever order the data arrives in.