Trie

Think about the search bar on a phone or website. As soon as you type:

ca

you might start seeing suggestions such as:

cat
car
card
care
camera

All of these words share the same beginning. Instead of treating every word as completely independent, we can organize them around their shared characters.

A Trie is a tree-based data structure built specifically for this kind of problem.

A Trie stores strings character by character and is especially efficient when the problem involves prefixes.

Trie is pronounced “try.”

How a Trie Represents Words

Suppose we insert:

cat
car
card

A simplified Trie could look like:

Each path from the root represents characters in a word:

root → c → a → t = "cat"

root → c → a → r = "car"

root → c → a → r → d = "card"

Notice that cat, car, and card all share the path:

c → a

The Trie stores that common prefix once instead of creating completely separate structures.

Trie Nodes

A Trie is made up of nodes. Each node needs to know which characters can come next.

For lowercase English letters, there are 26 possible next characters:

a → 0
b → 1
c → 2
...
z → 25

A simple Java node can therefore be represented as:

class TrieNode {

    TrieNode[] children =
        new TrieNode[26];

    boolean isEndOfWord;
}

The children array points toward the next possible characters.

The isEndOfWord field is equally important because a path can represent a prefix without representing a complete word.

For example, if we store:

apple

then:

app

is a valid prefix, but it may not be a complete word that we inserted.

So the node for p needs to know whether a word actually ends there.

The Root Node

Every Trie starts with a root.

The root doesn't represent a character. It simply provides the starting point for all stored strings.

For example:

root
 |
 c
 |
 a
 |
 t

The path from the root represents "cat".

Inserting a Word

Let's insert:

cat

We begin at the root and process one character at a time.

First comes:

Then:

Finally, we mark the t node as the end of a complete word.

Conceptually:

root
 |
 c
 |
 a
 |
 t*

The * means:

isEndOfWord = true

In Java, the insertion operation can be written as:

class Trie {

    TrieNode root;

    Trie() {
        root = new TrieNode();
    }

    void insert(String word) {

        TrieNode current = root;

        for (char ch : word.toCharArray()) {

            int index = ch - 'a';

            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }

            current = current.children[index];
        }

        current.isEndOfWord = true;
    }
}

The expression:

int index = ch - 'a';

converts a lowercase character into an array index.

For example:

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

So the character c is stored at:

children[2]

Now suppose we insert:

cat
car
card

After inserting cat:

root
 |
 c
 |
 a
 |
 t*

When inserting car, we don't create another c and a.

Those nodes already exist.

We simply continue from them:

When card is inserted, the existing c → a → r path is reused:

This sharing of common prefixes is one of the defining characteristics of a Trie.

Searching for a Word

Suppose the Trie contains:

cat
car
card

and we want to search for:

car

We follow:

c → a → r

If all three nodes exist, we then check:

current.isEndOfWord

If it is true, "car" was actually stored as a complete word.

A Java implementation is:

boolean search(String word) {

    TrieNode current = root;

    for (char ch : word.toCharArray()) {

        int index = ch - 'a';

        if (current.children[index] == null) {
            return false;
        }

        current = current.children[index];
    }

    return current.isEndOfWord;
}

That final isEndOfWord check matters.

Suppose only:

apple

was inserted.

The path for:

app

exists, but that doesn't mean "app" was inserted as a complete word.

So:

Path exists      → Prefix exists
isEndOfWord=true → Complete word exists

Checking a Prefix

A Trie becomes particularly useful when we don't need to find a complete word.

Suppose we have:

cat
car
card
care
dog

and ask:

Does any stored word start with "car"?

We only need to follow:

c → a → r

If that path exists, then "car" is a valid prefix.

We don't care whether the final node has isEndOfWord = true.

In Java:

boolean startsWith(String prefix) {

    TrieNode current = root;

    for (char ch : prefix.toCharArray()) {

        int index = ch - 'a';

        if (current.children[index] == null) {
            return false;
        }

        current = current.children[index];
    }

    return true;
}

Therefore:

startsWith("car");

returns:

true

while:

startsWith("xyz");

returns:

false

A Complete Trie Implementation

Here is a basic Trie supporting insertion, complete-word searching, and prefix searching:

class TrieNode {

    TrieNode[] children =
        new TrieNode[26];

    boolean isEndOfWord;
}

class Trie {

    TrieNode root;

    Trie() {
        root = new TrieNode();
    }

    void insert(String word) {

        TrieNode current = root;

        for (char ch : word.toCharArray()) {

            int index = ch - 'a';

            if (current.children[index] == null) {
                current.children[index] =
                    new TrieNode();
            }

            current = current.children[index];
        }

        current.isEndOfWord = true;
    }

    boolean search(String word) {

        TrieNode current = root;

        for (char ch : word.toCharArray()) {

            int index = ch - 'a';

            if (current.children[index] == null) {
                return false;
            }

            current = current.children[index];
        }

        return current.isEndOfWord;
    }

    boolean startsWith(String prefix) {

        TrieNode current = root;

        for (char ch : prefix.toCharArray()) {

            int index = ch - 'a';

            if (current.children[index] == null) {
                return false;
            }

            current = current.children[index];
        }

        return true;
    }
}

We can use it like this:

class Main {

    public static void main(String[] args) {

        Trie trie = new Trie();

        trie.insert("cat");
        trie.insert("car");
        trie.insert("card");

        System.out.println(
            trie.search("car")
        );

        System.out.println(
            trie.search("can")
        );

        System.out.println(
            trie.startsWith("ca")
        );
    }
}

Output:

true
false
true

Time Complexity

If the length of the word or prefix is L, the basic Trie operations take:

Insert       → O(L)
Search       → O(L)
Prefix Search → O(L)

Why?

Because the Trie processes one character at a time.

For example, searching:

cat

requires following:

c
a
t

So the number of operations depends primarily on the string's length.

Space Complexity

The major drawback of a Trie is memory consumption.

With:

TrieNode[] children = new TrieNode[26];

every node has room for 26 child references.

If many words have different prefixes, the Trie may require a large number of nodes.

On the other hand, shared prefixes can reduce duplication.

So the trade-off is roughly:

Trie
→ Excellent prefix operations
→ Potentially high memory usage

Compared with:

HashSet / HashMap
→ Often simpler
→ Usually less memory-intensive
→ Not naturally designed for prefix queries

Trie vs HashSet

Suppose we have:

cat
car
card
care
dog

A HashSet<String> is excellent for asking:

Does "car" exist?

But if we ask:

What words begin with "car"?

a HashSet doesn't naturally represent that prefix relationship.

A Trie does:

root
 |
 c
 |
 a
 |
 r
 / \
d   e

The shared path itself represents the prefix.

So the basic distinction is:

HashSet → Exact membership
Trie     → Exact membership + Prefix operations

Trie vs HashMap

A HashMap is designed around:

Key → Value

For example:

"cat" → 10
"car" → 20

It can perform exact key lookups efficiently.

A Trie instead organizes strings according to their characters:

First character
      ↓
Second character
      ↓
Third character
      ↓
...

So their primary strengths differ:

HashMap → Key-value lookup
Trie    → Character and prefix-based lookup

Autocomplete

One of the most recognizable uses of a Trie is autocomplete.

Imagine a search box containing a dictionary of:

cat
car
card
care
camera

The user types:

ca

The Trie takes us to:

root → c → a

From that node, we can explore the remaining branches and find possible completions:

cat
car
card
care
camera

This makes Tries particularly suitable for autocomplete systems.

Spell Checking

A Trie can also represent a dictionary of valid words:

apple
banana
computer
developer

When a user enters:

computr

the Trie can help determine whether that exact word exists.

More advanced algorithms can then be combined with the Trie to find similar words for correction.

The important point here is that the Trie gives us an efficient representation of the dictionary.

Longest Common Prefix

Tries are also useful for problems involving common prefixes.

Consider:

flower
flow
flight

The longest common prefix is:

fl

A Trie naturally represents shared beginnings:

root
 |
 f
 |
 l
 / \
o   i

The path shared by all words before the structure branches represents their common prefix.

A Trie can be extended to store additional information at each node.

For example:

int prefixCount;

Suppose we store:

car
card
care

At the node representing:

car

we could store:

prefixCount = 3

That allows us to answer questions such as:

How many stored words start with "car"?

with the appropriate additional bookkeeping.

This is a common technique in more advanced Trie problems.

Binary Trie

A Trie doesn't have to work with alphabetic characters.

We can also build a Binary Trie using only:

0
1

For example:

101
100
110

can be represented using two possible branches at every level.

A binary Trie is especially useful for problems involving:

XOR
Maximum XOR
Bit manipulation
Binary numbers

For example, finding the pair of numbers that produces the maximum XOR is a classic application.

A binary Trie node can be as simple as:

class TrieNode {

    TrieNode[] children =
        new TrieNode[2];
}

Here:

children[0] → bit 0
children[1] → bit 1

The underlying idea is exactly the same as a normal Trie.

Trie vs Binary Search Tree

A Binary Search Tree organizes values according to comparisons:

Smaller → Left
Larger  → Right

A Trie organizes strings one character at a time.

For example:

while a Trie might look like:

root
 |
 c
 |
 a
 / \
t   r

So:

BST  → Ordered values
Trie → Character/prefix structure

They're both tree-based structures, but they solve different types of problems.

Practical Applications

Tries are useful whenever strings and prefixes are central to the problem.

Common examples include:

Autocomplete
Dictionary lookup
Prefix searching
Spell checking
Longest common prefix
Word-search problems
Prefix-frequency queries
Binary XOR problems

The important question to ask in a DSA problem is:

"Do I need to work with prefixes rather than just exact values?"

If yes, a Trie may be a strong candidate.

The Main Idea

A Trie stores strings as paths through a tree:

which can represent:

cat
car
card

Its core operations are:

insert()       → O(L)
search()       → O(L)
startsWith()   → O(L)

where L is the length of the word or prefix.

The central idea is shared prefixes:

cat
car
card

c → a

and:

car
card

c → a → r

A Trie organizes strings character by character, making it especially powerful for prefix-based operations such as autocomplete, dictionary lookup, and prefix searching.

Keep this distinction in mind:

HashSet → Exact lookup
HashMap → Key-value lookup
BST     → Ordered lookup
Trie    → Prefix-based string lookup

Once the basic Trie is clear, more advanced problems can build on the same structure, including Trie deletion, prefix counting, autocomplete, word search, and Binary Tries for maximum-XOR problems.

How a Trie Represents Words

Trie Nodes

The Root Node

Inserting a Word

Sharing Prefixes

Searching for a Word

Checking a Prefix

A Complete Trie Implementation

Time Complexity

Space Complexity

Trie vs HashSet

Trie vs HashMap

Autocomplete

Spell Checking

Longest Common Prefix

Counting Words Sharing a Prefix

Binary Trie

Trie vs Binary Search Tree

Practical Applications

The Main Idea