Trie (Prefix Tree) — Step-by-Step Word Insertion & Autocomplete

Module 11 — Trie & Advanced: A tree built specifically for storing and searching strings Structured as Topic → Plain-English Explanation → Real Code → Visual Diagram → Complexity → Common Pitfalls.

1. Trie Concept & Internal Architecture

A Trie (derived from "retrieval", pronounced "try") is an $m$-ary tree data structure where each node represents a character along a prefix path. Unlike a hash map, keys that share common prefixes share the same parent nodes in memory.

Key Structural Properties

1. The root node represents an empty string "".
2. Each node contains an array or hash map of pointers to child nodes (typically size 26 for lowercase English letters 'a' through 'z').
3. Each node maintains a boolean flag isEndOfWord to distinguish between complete words and intermediate prefixes.

struct TrieNode {
    TrieNode* children[26];
    bool isEndOfWord;

    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
    }
};

2. Complete C++ Implementation: Insert, Search & StartsWith

class Trie {
private:
    TrieNode* root;

public:
    Trie() {
        root = new TrieNode();
    }

    // 1. Insert a word: O(L) Time, where L = word.length()
    void insert(const string& word) {
        TrieNode* curr = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!curr->children[idx]) {
                curr->children[idx] = new TrieNode();
            }
            curr = curr->children[idx];
        }
        curr->isEndOfWord = true;
    }

    // 2. Search exact full word: O(L) Time
    bool search(const string& word) {
        TrieNode* curr = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!curr->children[idx]) return false;
            curr = curr->children[idx];
        }
        return curr != nullptr && curr->isEndOfWord;
    }

    // 3. Prefix search (startsWith): O(P) Time, where P = prefix.length()
    bool startsWith(const string& prefix) {
        TrieNode* curr = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!curr->children[idx]) return false;
            curr = curr->children[idx];
        }
        return true;
    }
};

3. Autocomplete & Real-World System Use Cases

1. Search Engine Autocomplete: Type "algo" and the system traverses to node 'o', then runs a lightweight DFS/BFS to collect top-ranked completions ("algorithm", "algorand", "algorithmic trading").
2. Spell Checker & T9 Predictive Text: Validates whether a dictionary path exists in real-time.
3. IP Routing (Longest Prefix Match): Binary Tries with bits 0 and 1 efficiently match subnet masks in high-speed hardware routers.

4. Trie vs Hash Table Comparison