Trie Data Structure Explained — Implementation in C++ with Applications

A trie answers “does any word start with pre?” in about 2.8 nanoseconds, and it gives the same answer just as fast whether the dictionary holds a thousand words or seventy-six thousand. That is the property tries are built for, and it is why autocomplete works the way it does.

It is also the only benchmark below where the trie wins outright. For plain exact lookup a hash set matched it and used a tenth of the memory. This guide covers what a trie is, a complete modern C++ implementation of insert, search, prefix query and delete, and then the part most tutorials skip: the measured cost. Every program below was compiled and run for this article on Ubuntu 24.04 with GCC 13.3 under -std=c++17 with -Wall -Wextra, the implementation was exercised under AddressSanitizer and UndefinedBehaviorSanitizer, and every figure comes from a run against a 76,226-word English dictionary rather than an estimate.

Table of Contents

• The Short Answer
• What Is a Trie?
• The Key Property: Time Depends on the Key, Not the Set
• Implementing a Trie in C++
• Complexity
• What a Trie Actually Costs
• When to Use a Trie
• Key Takeaways
• Frequently Asked Questions
• Conclusion

The Short Answer

What is a trie? A tree where the path from the root spells out a key. Each node holds one character position, and words sharing a prefix share the nodes for that prefix.

When should I use one? When you need prefix operations — autocomplete, “does anything start with this”, longest-prefix matching. For plain “is this exact word in the set”, use a hash set.

What does it cost? Lookup is O(L) in the length of the key, independent of how many keys are stored. Memory is the trade: the classic array-of-26 layout measured 10× a std::unordered_set on the same dictionary.

What Is a Trie?

A trie is a tree data structure that stores strings by their characters, where each edge corresponds to one character and the path from the root to a node spells a prefix. Nodes do not store the key itself — the position in the tree defines it. Strings sharing a prefix share the nodes representing that prefix, so lookup takes time proportional to the length of the key rather than to the number of keys stored. It is also called a prefix tree, and the name comes from retrieval.

The structure was introduced by Edward Fredkin in a 1960 paper, which is also where the name comes from.

Two points of terminology worth getting right, because they are commonly confused:

• A trie is not a radix tree. A radix tree — also called a Patricia trie — is a compressed trie, where chains of single-child nodes are merged into one node holding a whole substring. Every radix tree is a compressed trie; a plain trie is not a radix tree.
• A trie is not a suffix tree. A suffix tree stores every suffix of one string, to answer substring queries. A trie stores a set of separate strings.

The Key Property: Time Depends on the Key, Not the Set

This is the claim that justifies the structure, and it is directly measurable. Probing for a prefix against dictionaries of three different sizes:

The trie column stays in the same low-single-digit-nanosecond band across a 76× increase in dictionary size, with no upward trend — it never compares against the other keys, it just walks three pointers. The tree column is not flat, because a balanced tree does O(log n) comparisons and each of those is a string comparison that may itself walk several characters.

That is the O(L) property, where L is the length of the key. It is the whole reason to reach for a trie, and every other trade-off in this article is the price of it.

Implementing a Trie in C++

A modern implementation, using std::unique_ptr so that destroying the root frees the whole structure with no manual cleanup.

#include <array>
#include <memory>
#include <string>
#include <vector>

class Trie {
    struct Node {
        std::array<std::unique_ptr<Node>, 26> child{};   // 'a'..'z'
        bool terminal = false;                            // a word ends here
    };
    std::unique_ptr<Node> root = std::make_unique<Node>();

    static int index(char c) { return c - 'a'; }
public:
    void insert(const std::string& word) {
        Node* n = root.get();
        for (char c : word) {
            int i = index(c);
            if (!n->child[i]) n->child[i] = std::make_unique<Node>();
            n = n->child[i].get();
        }
        n->terminal = true;
    }
};

Three decisions in that fragment matter.

terminal is a separate flag, not “has no children”. A word can end at a node that still has children — car ends inside the path to card. Without the flag there is no way to tell a stored word from a prefix of one.

The array is fixed at 26. That assumes lowercase a–z. It is the classic layout, it is the fastest, and it is also the source of the memory cost measured later. Passing anything else — an uppercase letter, a digit, a byte above 127 — makes index() return an out-of-range subscript, which is undefined behaviour, not a caught error. Real code needs either input validation at the public methods or a different child container.

std::unique_ptr owns the children. Destroying the root recursively destroys everything below it. A raw-pointer version needs a hand-written destructor, and that is the version that leaks.

Search: two different questions

    // Walks the prefix; returns nullptr if the path does not exist.
    const Node* descend(const std::string& s) const {
        const Node* n = root.get();
        for (char c : s) {
            int i = index(c);
            if (!n->child[i]) return nullptr;
            n = n->child[i].get();
        }
        return n;
    }

    bool contains(const std::string& word) const {
        const Node* n = descend(word);
        return n && n->terminal;          // the path exists AND a word ends here
    }

    bool startsWith(const std::string& prefix) const {
        return descend(prefix) != nullptr; // the path exists, that is all
    }

contains and startsWith do the same walk and differ only in the last line. That one line is the difference between “is this a word” and “could this become a word”.

Autocomplete

Once you have descended to the prefix node, every word beneath it is a completion. Collect them with a depth-first walk:

    static void collect(const Node* n, std::string& prefix,
                        std::vector<std::string>& out) {
        if (n->terminal) out.push_back(prefix);
        for (int i = 0; i < 26; ++i) {
            if (n->child[i]) {
                prefix.push_back(char('a' + i));
                collect(n->child[i].get(), prefix, out);
                prefix.pop_back();
            }
        }
    }

    std::vector<std::string> complete(const std::string& prefix) const {
        std::vector<std::string> out;
        const Node* n = descend(prefix);
        if (!n) return out;
        std::string buf = prefix;
        collect(n, buf, out);
        return out;
    }

The results come out in alphabetical order for free, because the loop visits children a through z in order.

Delete: the operation that is actually hard

Deleting must remove the word without disturbing any other word that shares its path. Deleting card from a trie containing car and carbon must leave both intact.

The approach is to recurse to the end of the word, clear the flag, then unwind — releasing each node only if it has become genuinely empty:

    // Returns true if `n` has become removable (no children, not terminal).
    static bool erase(Node* n, const std::string& word, std::size_t depth) {
        if (depth == word.size()) {
            if (!n->terminal) return false;   // word was never stored
            n->terminal = false;
        } else {
            int i = index(word[depth]);
            Node* next = n->child[i].get();
            if (!next || !erase(next, word, depth + 1)) return false;
            n->child[i].reset();              // child reported empty, release it
        }
        if (n->terminal) return false;        // another word ends here
        for (const auto& c : n->child) if (c) return false;   // another word passes through
        return true;                          // safe for the parent to drop
    }

    void remove(const std::string& word) { erase(root.get(), word, 0); }

The two guards before the final return true are the whole correctness argument: a node survives if a word ends at it, or if any word still passes through it.

Output, from the complete program compiled with -fsanitize=address,undefined:

contains("car")     = true
contains("ca")      = false   (a prefix, not a word)
startsWith("ca")    = true
contains("cargo")   = false

complete("car") -> car carbon card care 

after remove("card"):
  contains("card")  = false
  contains("car")   = true   (still there)
  contains("carbon")= true   (still there)

No sanitizer output on any run.

Complexity

The path operations — insert, contains, startsWith, remove — are independent of n, the number of stored keys. Only complete depends on anything else, and what it depends on is how many results it has to return. That is unusual and it is the point.

What a Trie Actually Costs

The old version of this article claimed a trie is “much more efficient than BST and hashing”. That is testable, so here it is tested. All figures below come from the same 76,226-word dictionary — 623,312 characters — on the machine described in the introduction.

Memory

Heap usage measured by replacing operator new and counting bytes requested. The comparison is against std::unordered_set, the hash set the old article claimed a trie would beat:

The array-of-26 trie used ten times the memory of a hash set holding the same words. Each node is 216 bytes, of which 208 is the pointer array — and most of those pointers are null. Swapping the array for a std::map that stores only the children that exist halves the memory, but the lookup cost is not a mild trade: on the same query set in a single binary, the map-based trie answered exact lookups in 558.5 ns against 36.7 ns for the array version — about 15× slower, because every level becomes a tree search instead of one indexed load.

Prefix sharing does work: 623,312 characters collapsed into 232,593 nodes, so 37% as many nodes as characters. The structure genuinely is compact in nodes. It is the fixed 26-pointer array in each node that is expensive.

Speed

Three results, and only one of them is the conventional answer.

For exact lookup the hash set won, narrowly — 21.3 ns against 23.4 ns — while using a tenth of the memory. The old claim that a trie beats hashing because it avoids computing a hash does not survive measurement: hashing a short string is cheap, and the trie’s pointer chase is not free either.

For “does any word start with this”, the trie won by 32× and the hash set cannot answer the question at all without scanning every element.

For enumerating every match, std::set beat the trie — 8.0 µs against 55.9 µs. That one surprised me. The reason is visible when you count the work: collecting 3,309 matches visited 10,875 trie nodes, about 3.3 nodes per result, each one a scan across 26 mostly-empty pointer slots. A std::set already holds its keys in sorted order, so the same query is a lower_bound followed by an in-order iterator walk that yields roughly one node per result. Fewer nodes touched and no 26-way scan at each one is enough to explain the gap without invoking anything more exotic.

All timings were compiled at -O2, taken with std::chrono::steady_clock against 2,000 queries split evenly between words that are present and words that are not, and reported as the mean of 200 repetitions for exact lookup and 20,000 for the prefix probes, with a volatile accumulator so the optimiser could not discard the work. These are still measurements of one implementation on one machine, not a general law. A more compact node layout would narrow the memory gap and speed up enumeration. The numbers to carry away are the shapes, not the constants: prefix existence is where the trie is structurally better, and memory is where it is structurally worse.

When to Use a Trie

Use one when the question is about prefixes:

• Autocomplete and type-ahead. Descend one node per keystroke and keep the pointer — each additional character costs one step, not a fresh search.
• Longest-prefix matching, as in IP routing tables and dictionary-based tokenisation — though production routing tables generally use a compressed radix variant rather than the one-character-per-node form shown here.
• Spell-check candidate generation, where you walk the trie allowing a bounded number of edits.
• “Is this a prefix of anything?” as a rejection test — being able to abandon an impossible branch after walking only its characters is why tries turn up inside word-game and crossword solvers. The 2.8 ns above is what that costs on this machine.

Reach for something else when:

• You only need exact lookup. A hash set matched the trie on speed and used a tenth of the memory.
• Memory is tight. Consider a radix tree, which merges single-child chains, or a std::map-based node.
• Keys are not strings and have no meaningful prefix structure.

For how the alternatives are built, see our guides to binary trees and the linked list in C, and the broader survey in top 10 algorithms every programmer should know.

Key Takeaways

• A trie’s lookup time depends on the key length, not the number of keys. Measured flat within noise from 1,000 to 76,226 words while std::set was not.
• Prefix existence is the trie’s real advantage — 2.8 ns against 91.1 ns for std::set, and a hash set cannot answer it at all.
• For exact lookup a hash set matched it, 21.3 ns against 23.4 ns, using a tenth of the memory. The claim that tries beat hashing does not survive measurement.
• Memory is the price. The array-of-26 layout measured 10× a std::unordered_set on the same words; a std::map-based node halves that.
• Prefix sharing is real: 623,312 characters became 232,593 nodes, 37% as many nodes as characters.
• Enumerating matches was faster with std::set in this test — 8.0 µs against 55.9 µs — because its in-order walk touches about one node per result, while the trie’s DFS touches 3.3 and scans 26 slots at each one.
• Delete is the operation to get right. A node survives if a word ends at it or any word still passes through it.
• A trie is not a radix tree and not a suffix tree. A radix tree is a compressed trie; a suffix tree indexes one string’s suffixes.

Frequently Asked Questions

Conclusion

The interesting thing about tries is that the textbook claim and the measurement disagree, and the disagreement is instructive. The claim is that a trie is faster because it never computes a hash. The measurement says a hash set matches it on exact lookup and costs a tenth of the memory — and that the trie’s genuine advantage is elsewhere, in the questions a hash set cannot answer at all.

That is the shape worth remembering. A trie is not a faster set; it is a different set, one that happens to keep every prefix of every key addressable. If your problem never asks about prefixes you are paying for structure you do not use. If it does — autocomplete, routing tables, a solver that needs to abandon impossible branches quickly — nothing else answers that question in time set by the length of the prefix rather than by how much you have stored. The rest of the data structures section covers the neighbouring ground.