Ugenz Academy/Tutorial

Trie

11 min read2,006 words

Reading progress

Keep learning

Trie

A Trie (pronounced "try") is a special tree data structure used mainly for storing and searching strings/prefixes.

It is also called a:

Prefix Tree

The main idea is:

Each path from the root represents characters of a word.

Tries are especially useful for prefix-based searching.

1. Why Do We Need a Trie?

Suppose we have these words:

apple app application apply banana ball bat

If we want to find all words beginning with:

app

a Trie is very useful.

It organizes the common prefix:

root | a | p | p / | \ l ? ...

The words:

app apple application apply

share:

app

A Trie stores this common part only once.

2. Basic Trie Structure

Suppose we insert:

cat car can

The Trie looks conceptually like:

root | c | a / | \ t r n

Notice that cat, car, and can share:

ca

So we don't store c and a separately for every word.

3. Trie vs Binary Tree

A normal binary tree has at most:

2 children

A Trie can have many children.

For lowercase English letters:

a b c d e f ... z

A node can have up to:

26 children

Example:

root / | \ a b c / \ p a

4. Important Trie Concepts

There are three important concepts:

Root

The starting node.

root

It does not represent a character.

Child

A character connected to another character.

End of Word

We need to know whether a path represents a complete word.

For example:

app apple

The path app exists in both words.

But:

app

must be marked as a complete word.

So we use:

isEndOfWord

5. Why isEndOfWord Is Important

Consider:

app apple

Trie:

root | a | p | p | l | e

How do we know whether app is a complete word?

We mark the second p:

root | a | p | p* ← complete word | l | e* ← complete word

So:

app → true apple → true

Without isEndOfWord, we wouldn't know whether app was actually inserted or was simply a prefix.

6. Trie Node in C++

For lowercase English letters:

struct TrieNode { TrieNode* children[26]; bool isEndOfWord; TrieNode() { isEndOfWord = false; for (int i = 0; i < 26; i++) { children[i] = nullptr; } } };

Each node has:

26 possible children + end-of-word information

7. Character to Array Index

Suppose:

a b c d ... z

We can convert characters to indexes using:

ch - 'a'

For example:

'a' - 'a' = 0 'b' - 'a' = 1 'c' - 'a' = 2

Therefore:

children[ch - 'a']

lets us access the appropriate child.

8. Inserting a Word

Suppose we insert:

cat

Start at root.

Character c

root | c

Character a

root | c | a

Character t

root | c | a | t*

Then:

isEndOfWord = true;

9. Insert Function

void insert(string word) { TrieNode* current = root; for (char ch : word) { int index = ch - 'a'; if (current->children[index] == nullptr) { current->children[index] = new TrieNode(); } current = current->children[index]; } current->isEndOfWord = true; }

10. Searching a Word

Suppose we inserted:

cat car can

Search:

cat

We follow:

root ↓ c ↓ a ↓ t

If we reach t and:

isEndOfWord == true

then:

cat exists

11. Search Function

bool search(string word) { TrieNode* current = root; for (char ch : word) { int index = ch - 'a'; if (current->children[index] == nullptr) { return false; } current = current->children[index]; } return current->isEndOfWord; }

12. Search vs Prefix Search

This is where Trie becomes powerful.

There are two different questions:

Question 1

Does the word app exist?

We need:

app exists as a complete word

Question 2

Does any word start with app?

We only need to know whether the path:

a → p → p

exists.

We don't care whether app itself is a complete word.

13. Prefix Search

Suppose the Trie contains:

apple application apply banana

Search prefix:

app

The path exists:

root | a | p | p

Therefore:

"app" is a valid prefix

C++ startsWith()

bool startsWith(string prefix) { TrieNode* current = root; for (char ch : prefix) { int index = ch - 'a'; if (current->children[index] == nullptr) { return false; } current = current->children[index]; } return true; }

14. Complete Trie Implementation

Here's a basic lowercase-English Trie:

#include <iostream> #include <string> using namespace std; struct TrieNode { TrieNode* children[26]; bool isEndOfWord; TrieNode() { isEndOfWord = false; for (int i = 0; i < 26; i++) { children[i] = nullptr; } } }; class Trie { private: TrieNode* root; public: Trie() { root = new TrieNode(); } void insert(string word) { TrieNode* current = root; for (char ch : word) { int index = ch - 'a'; if (current->children[index] == nullptr) { current->children[index] = new TrieNode(); } current = current->children[index]; } current->isEndOfWord = true; } bool search(string word) { TrieNode* current = root; for (char ch : word) { int index = ch - 'a'; if (current->children[index] == nullptr) { return false; } current = current->children[index]; } return current->isEndOfWord; } bool startsWith(string prefix) { TrieNode* current = root; for (char ch : prefix) { int index = ch - 'a'; if (current->children[index] == nullptr) { return false; } current = current->children[index]; } return true; } }; int main() { Trie trie; trie.insert("apple"); trie.insert("app"); trie.insert("application"); trie.insert("apply"); cout << trie.search("app") << endl; cout << trie.search("apple") << endl; cout << trie.search("banana") << endl; cout << trie.startsWith("app") << endl; cout << trie.startsWith("ban") << endl; return 0; }

Output:

1 1 0 1 0

Where:

1 = true 0 = false

15. Trie Complexity

Let:

L = length of the word

Then:

Insert

O(L)

Search

O(L)

Prefix Search

O(L)

This is one of the biggest advantages of Trie.

It depends mainly on the length of the word, not directly on the number of words stored.

16. Example

Suppose we have:

10,000,000 words

and want to search:

computer

The word has:

8 characters

Trie search follows approximately:

c → o → m → p → u → t → e → r

So the operation depends on:

L = 8

rather than checking millions of complete words one by one.

17. Trie vs Hash Table

Both can be useful for strings.

Hash Table

unordered_set<string>

Excellent for:

"Does this exact word exist?"

Average:

O(1)

Trie

Excellent for:

"Does this prefix exist?" "What words start with 'app'?"

Complexity:

O(L)

So:

Hash Table → Exact lookup Trie → Prefix lookup

18. Autocomplete

One of the most common real-world applications.

Suppose you type:

app

Google/search engine can suggest:

apple application apply app store

A Trie can store:

apple application apply appstore

and use the prefix:

app

to find all matching words.

Conceptually:

root | a | p | p / | \ l l s | | | e y t...

This is why Tries are often called Prefix Trees.

19. Spell Checker

Suppose a dictionary contains:

cat car can computer coding

A spell checker can use a Trie to efficiently determine whether a word exists.

For:

comp

the Trie can also tell us that it is a valid prefix.

20. Word Search

Tries are useful in problems involving:

dictionary prefixes multiple words word search

For example:

Given: apple app ape bat ball Find all words beginning with: ap

Answer:

apple app ape

21. Trie for Lowercase Letters

Our implementation uses:

TrieNode* children[26];

So it supports:

a-z

If we need uppercase letters too, we could use:

52 children

Or use a map:

unordered_map<char, TrieNode*> children;

This can save memory when a node has only a few actual children.

22. Array vs Map Implementation

Array

TrieNode* children[26];

Advantages:

  • Fast
  • Simple
  • O(1) character access

Disadvantage:

  • Can consume more memory

unordered_map

unordered_map<char, TrieNode*> children;

Advantages:

  • Stores only characters that actually exist
  • Useful for larger character sets

Disadvantage:

  • More overhead
  • Hashing involved

23. Trie Deletion

Deletion is more complicated than insertion/search.

Suppose:

app apple

Trie:

a → p → p* → l → e*

If we delete:

apple

we should not delete the app path because:

app

is still a valid word.

So deletion must determine whether nodes are still needed.

24. Trie Deletion Idea

There are two things to consider:

Case 1

The word is a prefix of another word.

app apple

Deleting app:

app* → apple

We only change:

isEndOfWord = false

The nodes remain.

Case 2

The word has no other word using its path.

Then unnecessary nodes can be deleted.

25. Trie vs BST vs Heap

Now you have learned three important tree-based structures.

StructureMain Purpose
Binary TreeHierarchical data
BSTOrdered searching
HeapPriority / min-max
TrieStrings / prefixes

Think:

BST ↓ "Find this value efficiently" Heap ↓ "Give me highest/lowest priority" Trie ↓ "Find words/prefixes"

26. Trie vs Binary Search Tree

Suppose we store:

apple application apply

A BST compares complete strings:

"apple" < "application"?

A Trie instead follows characters:

a ↓ p ↓ p ↓ l ↓ ...

Therefore, Trie naturally represents shared prefixes.

27. Important Trie Problems

After learning the basics, common DSA problems include:

  1. Implement Trie
  2. Search a word
  3. Prefix search
  4. Insert words
  5. Delete a word
  6. Autocomplete
  7. Word dictionary
  8. Longest common prefix
  9. Word Search II
  10. Count words with a given prefix
  11. Count distinct substrings
  12. Maximum XOR using Binary Trie

The last one is particularly interesting:

Binary Trie

Instead of storing letters:

a-z

we store:

0 and 1

This is useful for XOR-related problems.

28. Important Mental Model

Think about a Trie like a road map of characters.

For:

cat car can

all three journeys start:

c → a

Then they split:

c | a / | \ t r n

So:

Common prefixes share the same path.

That's the core idea of a Trie.

🧠 Final Summary

Remember these points:

1. Trie = Prefix Tree. 2. Mainly used for strings. 3. Each edge/node represents a character. 4. Common prefixes share nodes. 5. isEndOfWord tells us whether a complete word ends there. 6. Insert → O(L) 7. Search → O(L) 8. Prefix → O(L) 9. Excellent for autocomplete and prefix searching. 10. Trie is different from BST: BST → ordered values Trie → characters/prefixes

Where:

L = length of the word/prefix

Your roadmap now reaches:

Binary Tree ↓ BST ↓ Heap ↓ Priority Queue ↓ Trie ↓ Graphs ↓ Graph Traversal

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy