Lesson 14 · Non-linear structures

Trie Operations and Applications

A Trie is a specialized tree that stores strings character by character, providing blazing fast prefix matching and autocomplete capabilities.

What a Node Has to Hold

Before tracing the operations, fix what a node contains, because every step below manipulates exactly these two fields.

A node needs a children mapping from a character to a child node, and a boolean isEndOfWord. The node stores no character of its own — the character is on the edge that reached it, or equivalently is the key under which its parent holds it. This trips people up when first implementing one: asking a node 'which letter are you?' has no answer.

The root is a node like any other, representing the empty prefix. It is never marked as a word end unless the empty string is deliberately stored.

For the children mapping, a fixed array of 26 works when the alphabet is known lowercase letters, indexed by c - 'a', and gives O(1) child access with no hashing. A hash map stores only the children that exist and suits larger or unknown alphabets. Both give O(1) lookup; the array is faster, the map is smaller on sparse tries.

Some implementations add a counter of how many words pass through each node. It costs one integer per node and makes deletion and prefix-counting far simpler, as the following sections show. If you have the choice, include it.

A node holds a children map and an isEndOfWord flag
Characters live on the edges, not in the nodes
Fixed arrays are faster; hash maps are smaller on sparse tries
An optional per-node word counter simplifies deletion

Insertion

Start a pointer at the root. For each character of the word in turn: if the current node already has a child under that character, follow it; if not, create a new empty node, store it under that character, and move into it.

After the final character, set isEndOfWord = true on the node you have arrived at. This step is what actually records the word, and omitting it produces a trie where every search returns false despite the paths being present.

Inserting 'car' into an empty trie creates three nodes and flags the third. Inserting 'card' afterwards follows all three existing nodes, creates only one new node for 'd', and flags it — so the shared prefix costs nothing extra. Inserting 'car' a second time creates nothing at all and simply re-sets a flag that is already true.

The cost is O(L) for a word of length L, allocating at most L nodes. Note this is independent of how many words the trie already holds — inserting into a trie of ten words and one of ten million costs the same.

If you are maintaining a word counter, increment it on every node passed through, including the root, and only when the word is genuinely new — check the end flag before deciding whether this is a fresh insertion.

Follow the child if it exists, otherwise create it
Set isEndOfWord after the last character — this is what stores the word
Shared prefixes are traversed, not duplicated
O(L) time, at most L new nodes, independent of dictionary size

Search and Prefix Search

Both operations perform the same walk and differ only in what they check at the end. This is worth seeing clearly, because it is what makes a trie the right structure for autocomplete.

The shared walk: start at the root, and for each character, move to the corresponding child. If at any point the child does not exist, the path is absent — return false immediately.

For search(word) — is this exact word stored? — completing the walk is not sufficient. Return the value of isEndOfWord on the node reached. If a trie contains only 'card', searching for 'car' completes the walk successfully but the flag is false, so the correct answer is that 'car' is not stored.

For startsWith(prefix) — does any stored word begin with this? — completing the walk is sufficient. Return true, ignoring the flag entirely, because the path existing means some word passes through here.

So the two functions differ by exactly one boolean check. Confusing them is the most common trie bug, and it produces a structure where every prefix is reported as a stored word.

Both are O(L). Neither allocates, and neither depends on n.

A subtlety worth stating: a failed search stops at the first missing character, so it is often much faster than L. This is why tries reject non-words very quickly, which matters for spell-checkers scanning large inputs.

The operations and what each checks
Operation	Walk	Then	Cost
`insert(word)`	Follow or create	Set `isEndOfWord`	O(L)
`search(word)`	Follow only	Return `isEndOfWord`	O(L)
`startsWith(p)`	Follow only	Return true	O(L)
`delete(word)`	Follow to the end	Clear the flag, prune upward	O(L)
`completions(p)`	Follow to the prefix	DFS the subtree	O(L + k)

Search and prefix search share the identical walk
search returns the end flag; startsWith ignores it
That single boolean is the whole difference between them
A failed search exits at the first missing character

Key reference

Terms, operations, and practical uses

Structure

Prefix SharingMultiple words that start with the same sequence of letters share the exact same nodes in the tree.
Child PointersA node does not hold a character; the edge to the child represents the character. Implemented as an array of 26 or a hash map.
Terminal FlagA boolean isWord flag inside the node that is true if the path from the root to this node constitutes a valid dictionary word.

Operations

InsertionIterate through characters of a string, creating new child nodes only when a path for a character doesn't already exist.
Word SearchTraverse the characters. If a path ends or the final node's terminal flag is false, the word does not exist.
Prefix SearchTraverse the characters. If the path exists, the prefix exists. All descendant nodes represent valid autocomplete suggestions.

Variants

Radix TrieAlso known as a Patricia Trie. Compresses non-branching paths into a single edge containing a string, saving immense memory.
Bitwise TrieInstead of characters, edges represent 0 or 1. Used heavily for finding Maximum XOR pairs in arrays.
Aho-CorasickA Trie augmented with 'failure links' (similar to KMP) allowing simultaneous search for multiple patterns in a text.

Implementation

Autocomplete from a trie

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_word = True
    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        words = []
        def collect(node, path):
            if node.is_word:
                words.append(prefix + path)
            for char, child in sorted(node.children.items()):
                collect(child, path + char)
        collect(node, '')
        return words

trie = Trie()
for word in ('car', 'cat'):
    trie.insert(word)
print('Completions of "ca":', ', '.join(trie.starts_with('ca')))

#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct TrieNode {
    TrieNode* children[26] = {nullptr};
    bool isWord = false;
};
class Trie {
    TrieNode* root = new TrieNode();
    void collect(TrieNode* node, string prefix, vector<string>& out) {
        if (node->isWord) out.push_back(prefix);
        for (int c = 0; c < 26; c++)
        if (node->children[c]) collect(node->children[c], prefix + char('a' + c), out);
    }
    public:
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (!node->children[c - 'a']) node->children[c - 'a'] = new TrieNode();
            node = node->children[c - 'a'];
        }
        node->isWord = true;
    }
    vector<string> startsWith(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            if (!node->children[c - 'a']) return {};
            node = node->children[c - 'a'];
        }
        vector<string> out;
        collect(node, prefix, out);
        return out;
    }
};
int main() {
    Trie trie;
    trie.insert("car");
    trie.insert("cat");
    vector<string> words = trie.startsWith("ca");
    cout << "Completions of \"ca\": ";
    for(size_t i = 0; i < words.size(); i++) {
        if (i) cout << ", ";
        cout << words[i];
    }
    cout << '\n';
}

import java.util.*;
public class Main {
    static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isWord = false;
    }
    static class Trie {
        TrieNode root = new TrieNode();
        public void insert(String word) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                if (node.children[c - 'a'] == null) node.children[c - 'a'] = new TrieNode();
                node = node.children[c - 'a'];
            }
            node.isWord = true;
        }
        public List<String> startsWith(String prefix) {
            TrieNode node = root;
            for (char c : prefix.toCharArray()) {
                if (node.children[c - 'a'] == null) return List.of();
                node = node.children[c - 'a'];
            }
            List<String> out = new ArrayList<>();
            collect(node, prefix, out);
            return out;
        }
        private void collect(TrieNode node, String prefix, List<String> out) {
            if (node.isWord) out.add(prefix);
            for (int c = 0; c < 26; c++)
            if (node.children[c] != null) collect(node.children[c], prefix + (char) ('a' + c), out);
        }
    }
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("car");
        trie.insert("cat");
        System.out.println("Completions of \"ca\": " + String.join(", ", trie.startsWith("ca")));
    }
}

Watch it run

Step through it

Running on insert "car" and "cat", complete "ca"

Output

Read all 13 Steps

Empty trie A trie starts as a single root holding no character. Every word is a path down from here.
Insert c No child for 'c' exists, so create it. Edges carry the characters, not the nodes.
Insert a Descend and create 'a' below 'c'.
Insert r Create 'r'. This node ends a real word, so mark is_word = true on it.
Insert 'cat' Now insert 'cat'. Walk from the root: 'c' already exists, so reuse it.
Shared prefix 'a' exists too. Two words share this path — that shared prefix is the whole point of a trie.
Branch at t 't' does not exist under 'a', so create it and mark it as a word end. The trie now branches.
Search 'car' Search walks the same path, one character per level: c → a → r.
Found The path exists AND the final node is marked as a word. Cost is O(L) — length of the word, not the size of the dictionary.
Search 'ca' Now search for 'ca'. The path exists — but the node for 'a' has no word mark.
Why the flag matters 'ca' is a prefix of two words but is not itself a word. Without is_word a trie cannot tell those apart.
Prefix query 'ca' startsWith('ca') stops at the same node but only asks whether it exists — no flag check.
Autocomplete Everything below that node is a completion. Collect the subtree and you get 'car' and 'cat' — this is how autocomplete works.

Deletion, Case by Case

Deletion is the only trie operation with real subtlety, because a node on the word's path may still be needed by other words. Removing nodes unconditionally silently destroys stored data.

Walk to the node representing the last character of the word. If the path does not exist, or the flag is already false, the word was never stored and there is nothing to do.

Otherwise clear isEndOfWord. In many applications this is all that is needed — the word is now correctly reported as absent, and only some unused nodes remain.

To reclaim memory, walk back toward the root, removing a node only when both conditions hold: it has no children, and it is not itself the end of another word. Stop at the first node that fails either test; everything above it is still in use.

Three cases illustrate the rule. Deleting 'car' from a trie holding only 'car' removes all three nodes. Deleting 'car' from a trie holding 'car' and 'card' removes nothing — the 'r' node has a child, so the pruning stops immediately and only the flag changes. Deleting 'card' from that same trie removes only the 'd' node, because the 'r' node is now a word end for 'car' and must survive.

That middle case is the one deletion bugs get wrong, and it is worth stating in an exam answer as the reason the two conditions are both required.

If you maintain the per-node word counter, deletion becomes simpler and less error-prone: decrement the counter on every node along the path, and remove any node whose counter reaches zero. No case analysis, and no need to inspect children.

The cost is O(L) either way.

Clear the flag first; pruning is optional cleanup
Remove a node only if it is childless and not another word's end
Deleting 'car' where 'card' exists must remove no nodes at all
A word counter per node reduces this to decrement-and-drop-at-zero