Trie Operations

Table of Contents +

Say you are building the search box on an app like WhatsApp. A user types “ca”. You want to instantly show “cat”, “car”, and “card”. If you store words in a plain list, you have to scan every single word to find the ones that start with “ca”. That gets slow fast. A trie fixes this. A trie is a tree where each word is stored letter by letter. So words that share a starting part also share a path.

In this tutorial we look at the one building block that makes all of this work. That building block is the trie node. Then we write the insert operation that adds a word to the trie, walking it letter by letter.

📚 What Is a Trie Node?

A trie is made of many small pieces called nodes. A trie node is one spot in the tree. It stands for a single character along the way to a word.

Each node carries two things:

Child links — a way to reach the next characters. Think of it as a small map from a character to the node that comes after it. So from the node after “c”, a link labelled “a” takes you to the node for “ca”.
An isEndOfWord flag — a true or false value. It tells you whether the path from the root down to this node spells a complete word, not just a part of one.

Now here is something that surprises people. The character itself is not really stored inside the node. The character is the label on the link that got you there. The node just holds the links going out and that one flag.

Let me show you a trie that has the words “cat” and “car” in it.

See how “cat” and “car” share the path c -> a? They only split at the last letter. That sharing is what makes a trie fast. It also saves space.

🎯 How the Operations Walk the Word

Every trie operation works the same way. You start at the root and you walk one character at a time.

Here is the walk for inserting a word:

Start at the root node. This is the empty starting point above all words.
Take the first character of the word. Look in the current node’s child links for that character.
If a link for that character already exists, just step into that child node.
If there is no link yet, create a fresh node. Attach it under that character. Then step into it.
Move to the next character and repeat until the word is finished.
At the last node, set isEndOfWord to true. This marks that a full word ends right here.

That last step matters a lot. Without the flag, you could not tell “car” apart from “ca”. “car” is a real word you added. “ca” is just a part you walked through on the way.

Tip

A prefix just means the starting part of a word. “ca” is a prefix of both “cat” and “car”. The whole point of a trie is that shared prefixes share the same path. So you store them once.

🛠️ Steps to Insert a Word

Let me put the insert into clear steps before we write code.

Create the trie node type. It holds a map of child links and a boolean isEndOfWord set to false.
Make a root node. The trie always begins from this single empty node.
To insert a word, set a pointer called current to the root.
Loop over each character of the word.
For the current character, check if current has a child link for it.
If it does not, create a new node and store it under that character.
Move current down to that child node.
After the loop ends, set current.isEndOfWord to true.

💻 Defining the Node and Inserting a Word

Now the code. We define a trie node, build a small trie, and insert two words that share a prefix. Then we print whether each word was added. We check a word by walking it the same way and reading the flag at the end.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

# A trie node: a dict of child links and an end-of-word flag.
class TrieNode:
    def __init__(self):
        self.children = {}        # maps a character to the next TrieNode
        self.is_end_of_word = False

# Walk the word letter by letter, creating nodes when missing.
def insert(root, word):
    current = root
    for ch in word:
        if ch not in current.children:
            current.children[ch] = TrieNode()
        current = current.children[ch]
    current.is_end_of_word = True     # mark the full word

# Walk the word and return True only if it ends on an end-of-word node.
def search(root, word):
    current = root
    for ch in word:
        if ch not in current.children:
            return False
        current = current.children[ch]
    return current.is_end_of_word

root = TrieNode()
insert(root, "cat")
insert(root, "car")
print("cat added?", "yes" if search(root, "cat") else "no")
print("car added?", "yes" if search(root, "car") else "no")
print("ca added?", "yes" if search(root, "ca") else "no")

The output of the above code will be:

cat added? yes
car added? yes
ca added? no

Look at the “ca added? no” line. We did walk through the “ca” path while adding “cat” and “car”. But we never set the flag on the node for “a”. So the trie correctly says “ca” was not added as a word. That is the flag doing its job.

Note

Insert costs O(L) time, where L is the number of characters in the word. You touch one node per character, nothing more. Search costs O(L) too, for the same reason. The number of words already in the trie does not slow you down. That is the whole point.

⏱️ Complexity at a Glance

Here is the cost of each trie operation. L is the length of the word you are working with.

Operation	Time	Why
Insert a word	O(L)	One step per character of the word.
Search a word	O(L)	Walk the same path and read the end flag.
Create one node	O(1)	Just set up empty links and a false flag.

Caution

A common mistake is forgetting to set isEndOfWord at the end of insert. Then search walks the path fine but reads a false flag. So it reports the word as missing. Another common slip is reusing a node without checking the link first. That can wipe out words you already added. Always check for the link, and create only when it is missing.

🧩 What You’ve Learned

✅ A trie node holds two things: child links to the next characters and an isEndOfWord flag.
✅ The character is the label on the link, not a value stored inside the node.
✅ Every trie operation walks the word one character at a time, starting from the root.
✅ Insert creates a node only when the link for that character is missing, then sets the end flag on the last node.
✅ The isEndOfWord flag is what separates a real word from a prefix you only passed through.
✅ Insert and search both run in O(L) time, where L is the length of the word.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Introduction to Trie
Insert and Search in a Trie

Previous Introduction to Trie Next Insert and Search in a Trie

Share & Connect

Share on LinkedIn