Overview#

A Trie, also called a dictionary tree or prefix tree, is a data structure specifically designed for handling string prefixes. It breaks words into character paths, and words sharing the same prefix share the same segment of nodes.

If you frequently need to do things like “does a certain word exist,” “does a certain prefix exist,” or “autocomplete based on an input prefix,” a Trie is more natural than scanning strings one by one.

Its core idea is: use tree paths to represent strings.

Prerequisites

• Tree structure: each edge represents a character
• Hash map / array: node child links can be stored using a Map or an array
• Prefix matching: the query process goes down level by level along characters

Problem Definition#

Suppose there are three words:

1
cat
2
car
3
dog

The Trie organizes them as:

1
root
2
├─ c
3
│  └─ a
4
│     ├─ t (word)
5
│     └─ r (word)
6
└─ d
7
   └─ o
8
      └─ g (word)

This way, when querying the prefix ca, you only need to walk c -> a to know which words share this prefix.

Problems a Trie is suited for:

Here L is the word length, and n is the number of words.

Core Principle: Step-by-Step Diagram#

1
root -> c -> a -> t

Detailed Algorithm Steps#

A Trie node usually contains:

1
children: mapping from the current character to child nodes
2
isWord:   whether a complete word ends here

Insertion process:

1. Start from the root node;
2. Traverse each character of the word;
3. If the current character has no corresponding child node, create one;
4. Move to the child node;
5. After traversal ends, mark isWord = true.

The query process is similar, except that it does not create nodes; if it encounters a missing path, it directly returns failure.

TypeScript Implementation#

1
class TrieNode {
2
  readonly children = new Map<string, TrieNode>();
3
  isWord = false;
4
}
5

6
class Trie {
7
  private readonly root = new TrieNode();
8

9
  insert(word: string): void {
10
    let node = this.root;
11

12
    for (const char of word) {
13
      let next = node.children.get(char);
14

15
      if (!next) {
16
        next = new TrieNode();
17
        node.children.set(char, next);
18
      }
19

20
      node = next;
21
    }
22

23
    node.isWord = true;
24
  }
25

26
  search(word: string): boolean {
27
    const node = this.findNode(word);
28
    return node?.isWord ?? false;
29
  }
30

31
  startsWith(prefix: string): boolean {
32
    return this.findNode(prefix) !== null;
33
  }
34

35
  suggest(prefix: string, limit = 10): string[] {
36
    const start = this.findNode(prefix);
37
    if (start === null) return [];
38

39
    const result: string[] = [];
40

41
    const dfs = (node: TrieNode, path: string): void => {
42
      if (result.length >= limit) return;
43
      if (node.isWord) result.push(path);
44

45
      for (const [char, child] of node.children) {
46
        dfs(child, path + char);
47
      }
48
    };
49

50
    dfs(start, prefix);
51
    return result;
52
  }
53

54
  private findNode(text: string): TrieNode | null {
55
    let node = this.root;
56

57
    for (const char of text) {
58
      const next = node.children.get(char);
59
      if (!next) return null;
60
      node = next;
61
    }
62

63
    return node;
64
  }
65
}

Engineering Optimization: Compressed Trie#

A standard Trie may have many nodes, especially when strings are long and branching is sparse, producing many nodes with only one child.

For example:

1
root -> a -> p -> p -> l -> e

If intermediate nodes have no branching, they can be compressed into:

1
root -> "apple"

This kind of structure is called a compressed Trie or Radix Tree. It reduces the number of nodes, but the implementation is more complex, requiring handling the splitting and matching of string fragments.

Whether to compress in engineering depends on data scale, memory pressure, and query performance requirements.

Applications and Limitations#

Summary#

• A Trie uses tree paths to represent strings.
• Shared prefixes are the core advantage of a Trie.
• search requires a complete word to exist, while startsWith only requires the path to exist.
• Autocomplete can first locate the prefix node, then traverse the subtree.
• When the data volume is large, pay attention to the number of nodes and compression strategy.