Trie (Prefix Tree)

A trie stores strings by sharing their common prefixes. Each edge represents a character; following a path from the root spells a prefix. A terminal marker distinguishes a stored complete word from a prefix that merely exists on the way to a longer word. Tries make insertion, exact lookup, and prefix lookup depend on string length rather than the number of stored words. They are useful for dictionaries, autocomplete, prefix counting, and as a foundation for Aho–Corasick. This lesson handles nonempty lowercase English words and records duplicates as a multiset.

Prerequisites: Strings, arrays, dynamic vectors, rooted-tree terminology.

Build the idea

1. One node per distinct prefix

   The root represents the empty prefix. Inserting cat creates c, ca, cat; inserting car reuses c and ca and creates only car. Inserting dog follows an independent branch. A node's child[0..25] contains indices for its outgoing characters. Index 0 is the root and also the absent-child sentinel; newly allocated nonroot nodes always have positive indices.

2. Terminal counts and prefix counts

   Node terminal counts how many inserted words end exactly there. Node pass counts how many inserted words pass through that prefix, including words ending there. Inserting cat twice and car once makes pass(ca)=3, terminal(cat)=2, and terminal(ca)=0. The root's pass counts all words. Without a terminal marker, searching ca would incorrectly succeed just because cat exists.

3. Insert and search carefully

   For insertion, start at the root, increase its pass, and read characters left to right. Allocate a missing edge, move to its child, and increase that node's pass. Finally increase terminal. Exact lookup follows the same path without allocation and returns terminal. Prefix lookup returns pass. A missing edge means the answer is zero immediately; no further traversal is necessary.

4. Worked queries

   Insert cat, car, cat, dog. FIND cat prints 2; FIND ca prints 0; PREFIX ca prints 3; PREFIX z prints 0. These outputs illustrate both duplication and the difference between a complete word and a prefix. Trie structure alone determines spelling; counters supply multiplicities. The implementation does not silently insert missing words during queries.

5. Memory and implementation choices

   The fixed alphabet makes each node contain 26 child indices. This is predictable and fast but may consume substantial memory when strings share few prefixes. Sparse maps reduce empty links at extra overhead. During vector growth, references and pointers into its elements can become invalid. The code copies a new index into the vector before emplacing the new node and keeps only integer indices across allocation. Deletion is omitted; it would need to verify existence and decrement all counters along the path.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<array>
#include<string>
using namespace std;
struct Node{
    array<int,26>child{};
    int pass=0,terminal=0;
};
struct Trie{
    vector<Node>t=vector<Node>(1); // Root is node 0.
    void insert(const string&s){
        // pass counts occurrences with this prefix, including repeated words.
        int v=0;
        t[v].pass++;
        for(char c:s){
            int letter=c-'a';
            if(t[v].child[letter]==0){
                int next=(int)t.size();
                t[v].child[letter]=next; // Store before vector can grow.
                t.emplace_back();
            }
            v=t[v].child[letter];
            t[v].pass++;
        }
        // A path may be only a prefix; terminal marks complete stored words.
        t[v].terminal++;
    }
    int walk(const string&s)const{
        int v=0;
        for(char c:s){
            int next=t[v].child[c-'a'];
            // Queries never allocate missing prefixes.
            if(next==0){
                return -1;
            }
            v=next;
        }
        return v;
    }
    // Exact lookup counts endings; prefix lookup counts all traversing words.
    int exact(const string&s)const{
        int v=walk(s);
        return v<0?0:t[v].terminal;
    }
    int prefix(const string&s)const{
        int v=walk(s);
        return v<0?0:t[v].pass;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin>>q;
    Trie trie;
    while(q--){
        string op,s;
        cin>>op>>s;
        if(op=="ADD"){
            trie.insert(s);
        }
        else if(op=="FIND"){
            cout<<trie.exact(s)<<'\n';
        }
        else{
            cout<<trie.prefix(s)<<'\n';
        }
    }
}

Complexity analysis

Insertion, exact search, and prefix count each take O(L), where L is the query string length, with constant alphabet size 26. At most S+1 nodes exist after S total inserted characters; storage is O(26S)=O(S) for this fixed alphabet. Initializing every new node costs 26 constant-sized entries.

Example input and output

q commands ADD word, FIND word, or PREFIX word. Words are nonempty lowercase a–z; q and all multiplicities fit int.

Input

8
ADD cat
ADD car
ADD cat
ADD dog
FIND cat
FIND ca
PREFIX ca
PREFIX z

Output

2
0
3
0

cat was inserted twice, ca is not a complete stored word, three inserted words begin with ca, and none begin with z.

Practical applications

Dictionary lookups; autocomplete prefix counts; lexicographic traversal; prefix-based grouping. Bitwise tries apply a similar idea to integer bits but are a different implementation.

Check your understanding

What distinguishes the word car from the prefix ca?

Put it into practice

Implement deletion of one occurrence while keeping prefix counts correct.