Trie

Status

This note is complete, reviewed, and considered stable.

A Trie (pronounced "try"), also known as a Prefix Tree, is a tree-based data structure used to efficiently store and search strings.

Unlike Binary Search Trees, which organize data using value comparisons, a Trie organizes data character by character. Strings that share a common prefix share the same path in the tree.

Tries are commonly used for:

• Autocomplete systems
• Spell checkers
• Dictionaries
• Search suggestions
• IP routing
• Word games

Why Do We Need a Trie?

Consider storing the following words:

cat
car
can

A hash table can tell us whether a word exists, but it cannot efficiently answer questions like:

Words starting with "ca" ?

A Trie is specifically designed for prefix-based operations.

Trie Structure

Each node represents a character.

The path from the root to a node forms a prefix.

A special marker is used to indicate the end of a complete word.

Example

Words:

cat
car
can

Notice how all three words share the prefix:

ca

Trie Node Structure

A typical Trie node contains:

children
isEndOfWord

Conceptual Representation

TrieNode
├── children
└── isEndOfWord

Example Trie

Words:

cat
car
care
dog

Common Trie Operations

Insert

To insert a word:

1. Start at the root.
2. Process each character.
3. Create nodes if they do not exist.
4. Mark the last character as a complete word.

Insert "cat"

Time Complexity

O(m)

where:

m = length of word

Search

To search for a word:

1. Start from the root.
2. Follow the path for each character.
3. If any character is missing, the word does not exist.
4. Verify that the final node is marked as a complete word.

Example

Searching:

cat

Path:

Root → c → a → t

Result:

Found

Time Complexity

O(m)

Prefix Search

One of the biggest advantages of a Trie.

Question:

Does any word start with "ca"?

Traversal:

Root → c → a

If the path exists:

Prefix Exists

No need to traverse the entire tree.

Time Complexity

O(m)

Deletion

Deletion is more complicated than insertion and search.

Consider:

car
care

Deleting:

care

should not remove:

car

Before Deletion

After Deletion

The node e can be removed because no other word uses it.

Time Complexity

O(m)

Prefix Sharing

The major strength of a Trie is prefix sharing.

Words:

apple
app
application
apply

All words reuse the same prefix:

app

Complexity Analysis

Let:

m = length of key

Operation	Complexity
Insert	O(m)
Search	O(m)
Prefix Search	O(m)
Delete	O(m)

Trie vs Hash Table

Feature	Trie	Hash Table
Search Word	O(m)	O(m)
Prefix Search	Efficient	Inefficient
Autocomplete	Excellent	Poor
Ordered Traversal	Yes	No
Memory Usage	Higher	Lower

Advantages

• Fast prefix search
• Efficient autocomplete
• Shared prefixes reduce duplication
• Predictable performance
• Naturally supports lexicographical traversal

Disadvantages

• High memory usage
• Large alphabet increases storage requirements
• More complex than hash tables

Variants of Trie

Compressed Trie (Radix Tree)

Chains of single-child nodes are compressed.

c → a → t

becomes:

cat

Reducing memory usage.

Ternary Search Trie

Combines ideas from:

• Trie
• Binary Search Tree

Suffix Trie

Stores all suffixes of a string.

Used in advanced string matching algorithms.