Trie

Prefix tree for string storage with insert, search, prefix check, and erase in O(|s|).

[Data Structures]|

Jul 9, 2026

|explanatory_notes.md|

#trie#prefix-tree#string#dictionary

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;

const int ALPHA = 26;

struct Trie {
    struct Node {
        int ch[ALPHA];
        int freq;
        bool isEnd;
    };

    vector<Node> t;

    Trie() { t.push_back({{}, 0, false}); }

    int newNode() { t.push_back({{}, 0, false}); return t.size() - 1; }

    void insert(const string& s) {
        int cur = 0;
        for (char c : s) {
            int idx = c - 'a';
            if (!t[cur].ch[idx]) t[cur].ch[idx] = newNode();
            cur = t[cur].ch[idx];
            t[cur].freq++;
        }
        t[cur].isEnd = true;
    }

    bool search(const string& s) {
        int cur = 0;
        for (char c : s) {
            int idx = c - 'a';
            if (!t[cur].ch[idx]) return false;
            cur = t[cur].ch[idx];
        }
        return t[cur].isEnd;
    }

    bool startsWith(const string& s) {
        int cur = 0;
        for (char c : s) {
            int idx = c - 'a';
            if (!t[cur].ch[idx]) return false;
            cur = t[cur].ch[idx];
        }
        return true;
    }

    void erase(const string& s) {
        if (!search(s)) return;
        int cur = 0;
        for (char c : s) {
            int idx = c - 'a';
            int nxt = t[cur].ch[idx];
            t[nxt].freq--;
            if (t[nxt].freq == 0) { t[cur].ch[idx] = 0; return; }
            cur = nxt;
        }
        t[cur].isEnd = false;
    }

    int countPrefix(const string& s) {
        int cur = 0;
        for (char c : s) {
            int idx = c - 'a';
            if (!t[cur].ch[idx]) return 0;
            cur = t[cur].ch[idx];
        }
        return t[cur].freq;
    }
};

72 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Trie (Prefix Tree)

Stores strings character by character. Each node has up to $|\Sigma|$ children and a word-end flag.

Operations

insert(s) — add string to trie

search(s) — check if exact string exists

startsWith(s) — check if any string has prefix

s

erase(s) — remove string, pruning dead branches

How It Works

Each node stores children[26], isEnd flag, and freq counter

Insertion follows/creates child pointers, incrementing freq

Erase decrements freq and deletes nodes that reach zero

When to Use

Prefix matching, autocomplete

Counting strings with a given prefix

Word dictionaries with fast lookup

Notes

Change ALPHA and offset for uppercase ('A') or digits ('0')

Complexity

All operations —

O(|s|)

Space —

O(\text{total characters} \cdot |\Sigma|)