Tries are ideal for prefix matching, autocomplete features, spell checkers, and IP routing where string keys share common prefixes.

Trie vs Hash Map performance?

Tries can be faster for prefix searches and avoid hash collisions. However, they use significantly more memory due to many node pointers.

How is Autocomplete implemented?

Autocomplete works by traversing the Trie to the prefix node and then finding all words in its subtree (usually via DFS).

Trie (Prefix Tree)

A trie (prefix tree) is a tree-based data structure for efficiently storing and retrieving keys in a dataset of strings.

GREEN = END OF A STORED WORD

READY

Insert words and watch shared prefixes get reused. A node marked as a word end is what separates a stored word from a mere prefix.

Word

Intuition

Think of a dictionary where you look up words letter by letter. A Trie (pronounced 'try') stores strings such that common prefixes are shared. For example, 'cat' and 'car' share the path 'c' -> 'a'.

Concept

Each node in a Trie represents a character. The root represents an empty string. Moving down from the root adds characters to the prefix. Some nodes are marked as endOfWord to indicate that the path from the root to that node forms a valid word.

How it Works

Root: Empty node, starting point.
Children: Map or array linking characters to next nodes.
EndOfWord: Boolean flag marking a complete string.
Insertion: Walk down, creating nodes if they don't exist.
Search: Walk down; if you get stuck, word doesn't exist.

Step-by-Step Breakdown

Insertion Logic:

Start at root.
For each character in the word:
- Check if child exists for that char.
- If not, create a new node.
- Move to child.
Mark the final node as isEnd = true.

When to Use

Autocomplete/Typeahead systems.
Spell checkers.
IP routing (Longest Prefix Match).
Solving word games (Boggle).

When NOT to Use

When strings are very long and unique (high space consumption).
When you only need full string matching: a hash set is simpler and usually faster in practice. Both take O(L) per lookup, since hashing a string reads every character, but a hash set has no per-character pointer chasing.

How to Identify

Keywords: "Prefix search", "Autocomplete", "Dictionary", "Word Search II".

Introduction to Tries (Prefix Trees)

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description

AVL Tree

Segment Tree

Complexity

Time (Best)

O(L)

Time (Average)

O(L)

Time (Worst)

O(L)

Space

O(N * L)

Trie (Prefix Tree) Code

1class TrieNode {
2    constructor() {
3        this.children = {};
4        this.isEnd = false;
5    }
6}
7
8class Trie {
9    constructor() {
10        this.root = new TrieNode();
11    }
12
13    insert(word) {
14        let node = this.root;
15        for (let char of word) {
16            if (!node.children[char]) {
17                node.children[char] = new TrieNode();
18            }
19            node = node.children[char];
20        }
21        node.isEnd = true;
22    }
23
24    search(word) {
25        let node = this.root;
26        for (let char of word) {
27            if (!node.children[char]) return false;
28            node = node.children[char];
29        }
30        return node.isEnd;
31    }
32
33    startsWith(prefix) {
34        let node = this.root;
35        for (let char of prefix) {
36            if (!node.children[char]) return false;
37            node = node.children[char];
38        }
39        return true;
40    }
41}

Related Lessons

Trie (Prefix Tree)

Intuition

Concept

How it Works

Step-by-Step Breakdown

When to Use

When NOT to Use

How to Identify

Sample Problems

Implement Trie (Prefix Tree)

Design Add and Search Words Data Structure

Word Search II

Introduction to Tries (Prefix Trees)

AI resume checker — match your resume to the job description

Stack

Queue

Deque

Circular Queue

Frequently Asked Questions

When to use a Trie?

Trie vs Hash Map performance?

How is Autocomplete implemented?