Introduction to Trie

Think about the search box on YouTube. You type just “how” and it already shows “how to cook rice”, “how to tie a tie”, “how old is…”. It feels instant, right? Now imagine the app kept every search word in one long list. To find all words starting with “how”, it would have to check every single word in that list, one by one. With millions of words, that is slow. A trie is the data structure that makes this kind of prefix search fast.

🎯 The Problem First

Say you have a big list of words. A user types a few letters. You want all the words that start with those letters.

With a plain list, you have no choice. You walk through the whole list and test each word. The longer the list, the slower it gets. And you repeat this work on every keystroke.

The real pain shows up in things like:

• Search suggestions that should update as you type
• Spell checkers that need to know if a word exists
• Contact search that filters names while you type

A trie solves this. A trie is a tree built for storing strings. Words that share a starting part also share the same path in the tree. So finding everything that starts with “how” means walking down one short path. You never scan the whole list.

📚 A Real-World Analogy

Picture a library with one big sign at the entrance. It points you down hallways by letter. You want a book on “cat”. You walk through the door marked “C”. Then you reach a door marked “A”. Then “T”. You followed three doors and now you are exactly where all the “cat” books live.

Now your friend wants “car”. They start the same way. Through “C”, then “A”. Those are the same two doors you used. Only at the third step do they turn to “R” instead of “T”.

See the idea? Words that begin the same way walk the same hallways. They split apart only at the first letter where they differ. That shared walking is the whole secret of a trie.

🌳 What a Trie Actually Looks Like

The word “trie” comes from retrieval, because it is good at retrieving words. People also call it a prefix tree, because every path from the top spells out a prefix.

Here is a trie holding the words “cat”, “car”, “card”, and “dog”.

Walk through it slowly.

• The top is an empty starting point called the root. It holds no letter.
• Each line going down is one character.
• Follow root then “c” then “a” then “t” and you spelled “cat”.
• “cat” and “car” share the “c” then “a” path. They split only at the last letter.
• “card” just keeps going one more step after “car”.

So the same letters never get stored twice. The shared prefix is stored once and reused. That is why a trie saves both space and time on prefixed words.

🧩 What Lives Inside One Node

Every spot in the tree is a node, which is just one small box that holds two things.

• Links to children. Each node keeps a way to reach the next character. From the “a” node above, one link goes to “t” and another goes to “r”. A common way to store these links is a map from a character to the child node.
• An end-of-word flag. This is a simple true or false. It answers the question “does a real word end right here?”

Why do we need that flag? Look at “car” and “card”. When we walk down “c”, “a”, “r”, we land on a node. Is “car” a word? Yes. But the path keeps going to “d” for “card”. Without a flag, we could not tell that “car” is a complete word and not just the start of “card”.

Here is a tiny node shape in all five languages so you can picture the box. It is not a full trie yet, just the building block.

#include <stdio.h>
#include <stdbool.h>

// One trie node: 26 child links (a-z) and an end flag.
struct TrieNode {
    struct TrieNode *children[26];
    bool isEndOfWord;
};

int main(void) {
    struct TrieNode root;
    // Start with no children and not an end of any word.
    for (int i = 0; i < 26; i++) root.children[i] = NULL;
    root.isEndOfWord = false;

    printf("A node has 26 child links and isEndOfWord = %s\n",
           root.isEndOfWord ? "true" : "false");
    return 0;
}

A node has 26 child links and isEndOfWord = false

#include <iostream>
#include <unordered_map>
using namespace std;

// One trie node: a map from a character to a child node, plus an end flag.
struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord = false;
};

int main() {
    TrieNode root;
    cout << "Children stored so far: " << root.children.size() << "\n";
    cout << "Is this the end of a word? "
         << (root.isEndOfWord ? "yes" : "no") << "\n";
    return 0;
}

Children stored so far: 0
Is this the end of a word? no

import java.util.HashMap;

public class TrieNode {
    // A map from a character to the next node, plus an end-of-word flag.
    HashMap<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord = false;

    public static void main(String[] args) {
        TrieNode root = new TrieNode();
        System.out.println("Children stored so far: " + root.children.size());
        System.out.println("Is this the end of a word? " + root.isEndOfWord);
    }
}

Children stored so far: 0
Is this the end of a word? false

class TrieNode:
    def __init__(self):
        # A map from a character to the next node.
        self.children = {}
        # True only when a real word ends here.
        self.is_end_of_word = False


root = TrieNode()
print("Children stored so far:", len(root.children))
print("Is this the end of a word?", root.is_end_of_word)

Children stored so far: 0
Is this the end of a word? False

class TrieNode {
  constructor() {
    // A map from a character to the next node.
    this.children = new Map();
    // True only when a real word ends here.
    this.isEndOfWord = false;
  }
}

const root = new TrieNode();
console.log("Children stored so far:", root.children.size);
console.log("Is this the end of a word?", root.isEndOfWord);

Children stored so far: 0
Is this the end of a word? false

⚡ Why a Trie Is Faster Here

The big win is this. Looking up a word, or checking a prefix, depends only on how long that word is. It does not depend on how many words you stored.

If the word has L letters, you take L steps down the tree. That is it. Whether the trie holds ten words or ten million words, “how” is still just three steps.

Compare that with a plain list, where you might scan every word to find matches.

Here n is the number of words and L is the length of one word. Since L is usually small, a trie lookup feels instant.

One small note on that prefix row. Reaching the prefix branch takes O(L). Listing every word under that branch then costs a little more, based on how many matches there are. So the O(L) is the cost to get to the branch, not the cost of printing every match.

🛠️ Where You Have Already Met a Trie

You use tries all the time without noticing.

• Search autocomplete. Type a few letters in YouTube or Amazon and suggestions appear. A trie can fetch all words under that prefix quickly.
• Spell checkers. The app needs a fast yes-or-no on “is this a real word”. A trie answers in steps equal to the word length.
• Contact search. Type “ar” in your phone and “Arjun” and “Aryan” show up. The phone walks the trie path for “ar” and reads everything below it.

⚠️ Common Mistakes to Avoid

A few things trip people up when they first meet tries.

• Forgetting the end-of-word flag. Without it you cannot tell a finished word like “car” from the start of a longer word like “card”.
• Thinking the root holds a letter. The root is empty. The first real letter sits one step below it.
• Expecting a trie to save memory always. When words share very few prefixes, a trie can use more memory than a plain list, because it keeps many separate nodes.
• Mixing up a word and a prefix. Every word is a prefix of itself, but not every prefix is a stored word. The flag is what tells them apart.

🧩 What You’ve Learned

• ✅ A trie (prefix tree) stores strings as paths, where each edge is one character.
• ✅ Words that share a beginning share the same path, so prefixes are stored once.
• ✅ Each node holds links to child characters and an end-of-word flag.
• ✅ The root is empty; real letters start one level below it.
• ✅ Lookup and prefix checks cost about O(L), where L is the word length, no matter how many words are stored.
• ✅ Tries power autocomplete, spell checkers, and contact search.

🚀 What’s Next?

• Trie Operations
• Insert and Search in a Trie