Trie Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide

// Prefix tree: one node per prefix; children indexed by letter.
struct TrieNode {
    TrieNode* child[26] = {};
    bool isEnd = false;                       // a whole word ends here (not just a prefix)
};

class Trie {
    TrieNode* root = new TrieNode();

    // Walks the path for s; returns the last node, or nullptr if the path breaks.
    TrieNode* walk(const string& s) {
        TrieNode* cur = root;
        for (char c : s) {
            cur = cur->child[c - 'a'];
            if (!cur) return nullptr;
        }
        return cur;
    }

public:
    void insert(const string& word) {
        TrieNode* cur = root;
        for (char c : word) {
            if (!cur->child[c - 'a']) cur->child[c - 'a'] = new TrieNode();
            cur = cur->child[c - 'a'];
        }
        cur->isEnd = true;
    }
    bool search(const string& word) { TrieNode* n = walk(word); return n && n->isEnd; }
    bool startsWith(const string& prefix) { return walk(prefix) != nullptr; }
};

// Trie + DFS: when one letter can branch (a wildcard, a grid neighbour),
// try every child, but only along paths that exist in the trie.
// Here: search with '.' matching any one letter (LC 211).
struct TrieNode {
    TrieNode* child[26] = {};
    bool isEnd = false;
};

bool match(TrieNode* node, const string& pat, int i) {
    if (!node) return false;                  // the path broke: no word continues this way
    if (i == (int)pat.size()) return node->isEnd;
    if (pat[i] != '.') return match(node->child[pat[i] - 'a'], pat, i + 1);
    for (TrieNode* next : node->child)        // '.': any existing child may continue the match
        if (next && match(next, pat, i + 1)) return true;
    return false;
}

// Bitwise trie: store each number's bits from the highest down.
// For the largest XOR with x, prefer the OPPOSITE bit at every level: one higher bit
// is worth more than all lower bits together (2^b > 2^b - 1).
struct BitNode {
    BitNode* child[2] = {};
};

const int HIGH = 30;                          // values < 2^31

void insert(BitNode* root, int x) {
    BitNode* cur = root;
    for (int b = HIGH; b >= 0; b--) {
        int bit = (x >> b) & 1;
        if (!cur->child[bit]) cur->child[bit] = new BitNode();
        cur = cur->child[bit];
    }
}

// Largest x XOR y over all y in the trie (the trie must not be empty).
int bestXor(BitNode* root, int x) {
    BitNode* cur = root;
    int result = 0;
    for (int b = HIGH; b >= 0; b--) {
        int want = 1 - ((x >> b) & 1);        // the bit that makes this XOR bit 1
        if (cur->child[want]) { result |= 1 << b; cur = cur->child[want]; }
        else cur = cur->child[1 - want];
    }
    return result;
}