Trees · pattern 5 of 8

Trie

A trie is a tree of letters. Each step down from the top node, the root, is one letter, so words that begin the same share their first steps. A mark shows where a word ends. Looking up a word follows only that word's letters.

Watch it run in the app

When to use it

Use it when the questions are about how words begin: whether any stored word starts with some letters, or which stored word a text starts with.

It belongs to the trees group: Let the shape of the data do the work: the branches of a tree, the letters of a trie, the top of a heap.

Watch it work

An online game keeps a list of reserved words. A player name is refused if it begins with a reserved word. For each name asked for, return true if it is refused and false if it is allowed.

Input
reserved = ["mod", "mob", "bot"]
names = ["mobile", "moon", "robot", "mo", "bottle"]

Output
[true, false, false, false, true]

The method

Start with an empty root node
Add a word: follow its letters, making the missing nodes
Mark the node of its last letter as the end of a word
Walk a name's letters down from the root
A missing letter stops the walk: the name is allowed
An end mark stops the walk: the name is refused

The run, one moment at a time

Step 1. The tree starts as one empty node, the root, drawn as a dot. No word is stored yet.
```
reserved: mod mob bot
names: mobile moon robot mo bottle
answer: empty
```
Step 2. No stored word begins with m. Make a node for each letter of "mod": m, o and d, each under the one before.
```
reserved: mod mob bot
names: mobile moon robot mo bottle
answer: empty
```
Step 3. The walk ended on d. Mark that node as the end of a word, shown by a star after its letter. "mod" is now stored.
```
reserved: mod mob bot
names: mobile moon robot mo bottle
answer: empty
```
Step 2. "mob" begins like a word already stored: m and o are there. Follow them and make 1 new node: b.
```
reserved: mod mob bot
names: mobile moon robot mo bottle
answer: empty
```
Step 3. The walk ended on b. Mark that node as the end of a word, shown by a star after its letter. "mob" is now stored.
```
reserved: mod mob bot
names: mobile moon robot mo bottle
answer: empty
```
Step 2. No stored word begins with b. Make a node for each letter of "bot": b, o and t, each under the one before.
```
reserved: mod mob bot
names: mobile moon robot mo bottle
answer: empty
```
Step 3. Mark t as the end of a word. The 3 words have 9 letters, and the tree needs only 7 letter nodes, because a shared beginning is stored once.
```
reserved: mod mob bot
names: mobile moon robot mo bottle
answer: empty
```
Step 6. "mobile": m, o and b are in the tree, and b has an end mark. The name begins with "mob", so it is refused. The letters "ile" are never read.
```
reserved: mod mob bot
names: mobile moon robot mo bottle
answer: true
```
Step 5. "moon": m and o are in the tree, but under them there is no step for the next letter, o. No reserved word begins this name, so it is allowed.
```
reserved: mod mob bot
names: mobile moon robot mo bottle
answer: true false
```
Step 5. "robot": the root has no step for r, so the walk stops at once and the name is allowed. "bot" is inside the name, but the tree only knows how words begin.
```
reserved: mod mob bot
names: mobile moon robot mo bottle
answer: true false false
```
Step 4. "mo": m and o are in the tree, and the name has no more letters. No end mark was met on the way, so the name is allowed.
```
reserved: mod mob bot
names: mobile moon robot mo bottle
answer: true false false false
```
Step 6. "bottle": b, o and t are in the tree, and t has an end mark. The name begins with "bot", so it is refused. The letters "tle" are never read. Every name now has its answer.
```
reserved: mod mob bot
names: mobile moon robot mo bottle
answer: true false false false true
```

The code

The numbered comments are the steps of the method.

JavaScript

function solve(reserved, names) {
  // 1. Start with an empty root node
  const root = { end: false, children: new Map() };
  const answer = [];
  for (const word of reserved) {
    // 2. Add a word: follow its letters, making the missing nodes
    let node = root;
    for (const letter of word) {
      if (!node.children.has(letter)) {
        node.children.set(letter, { end: false, children: new Map() });
      }
      node = node.children.get(letter);
    }
    // 3. Mark the node of its last letter as the end of a word
    node.end = true;
  }
  for (const name of names) {
    // 4. Walk a name's letters down from the root
    let node = root;
    let refused = false;
    for (const letter of name) {
      // 5. A missing letter stops the walk: the name is allowed
      if (!node.children.has(letter)) break;
      node = node.children.get(letter);
      // 6. An end mark stops the walk: the name is refused
      if (node.end) {
        refused = true;
        break;
      }
    }
    answer.push(refused);
  }
  return answer;
}

Python

def solve(reserved, names):
    # 1. Start with an empty root node
    root = {"end": False, "children": {}}
    answer = []
    for word in reserved:
        # 2. Add a word: follow its letters, making the missing nodes
        node = root
        for letter in word:
            if letter not in node["children"]:
                child = {"end": False, "children": {}}
                node["children"][letter] = child
            node = node["children"][letter]
        # 3. Mark the node of its last letter as the end of a word
        node["end"] = True
    for name in names:
        # 4. Walk a name's letters down from the root
        node = root
        refused = False
        for letter in name:
            # 5. A missing letter stops the walk: the name is allowed
            if letter not in node["children"]:
                break
            node = node["children"][letter]
            # 6. An end mark stops the walk: the name is refused
            if node["end"]:
                refused = True
                break
        answer.append(refused)
    return answer

How to spot it

Asked: Does any stored word start with these letters?: Walk the letters down from the root. If every step is there, at least one stored word begins that way.
Given: Many words to look for at once, while letters come one at a time: Words that begin the same share one path. One walk down the tree follows every word that still fits the letters so far.
Asked: Match words letter by letter, where some letters are unknown: A known letter has one step down to take. An unknown letter tries every step, and a path that spells no word is dropped early.
Limits: Many stored words, and a question about a beginning must not read them all: A walk takes one step for each letter of the question. How many words are stored does not change that.

Looks like it, but is not

You only ask whether a whole word is in the collection, never how words begin. Use Hash set membership. A set finds a whole word in one step, with much less code. Build a trie only when the questions are about beginnings.
The problem speaks of a prefix, but of a list of numbers: the sum of the first few values. Use Prefix and suffix passes. There a prefix is a running total over positions in a list. In a trie a prefix is the first letters of a word.
The words are kept in sorted order, never change, and you look for one whole word. Use Binary search on a sorted range. Sorted order already finds a word in a few steps by halving. No tree of letters has to be built.

Cost and mistakes

Storing a word or asking about one takes one step for each of its letters, written O(L) for L letters, however many words are stored. Extra space is at most one node for every letter of every stored word.

Watch out

Do not forget the end mark. The path m, o is in the tree only because "mod" and "mob" pass through it. Without the mark, "mo" would look like a stored word.
A trie knows how a word begins, not what is inside it. "robot" contains "bot", and the walk still stops at its first letter.

In the 150

3 problems of the 150 use it. Naming them gives their method away, so the list is folded.

Show the 3

Implement Trie Prefix TreeMedium · Tries
Design Add And Search Words Data StructureMedium · Tries
Word Search IIHard · Tries