Tries

Reach for it when

• Prefix queries (startsWith, autocomplete)
• Many words searched in a grid or a stream
• Wildcard matching over a dictionary

Core idea

Each node holds a map from character to child plus an end-of-word flag. Insert and search cost O(length of word), independent of how many words are stored, and a DFS over the trie can prune an entire set of words the moment a prefix fails.

Template · O(L) per operation, O(total characters) space

class Trie:
    def __init__(self):
        self.root = {}
    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node["$"] = True                  # end of word
    def starts_with(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node:
                return False
            node = node[ch]
        return True

struct Trie {
    struct Node { array<Node*, 26> next{}; bool end = false; };
    Node* root = new Node();
    void insert(const string& word) {
        Node* node = root;
        for (char ch : word) {
            Node*& child = node->next[ch - 'a'];
            if (!child) child = new Node();
            node = child;
        }
        node->end = true;              // end of word
    }
    bool startsWith(const string& prefix) {
        Node* node = root;
        for (char ch : prefix) {
            node = node->next[ch - 'a'];
            if (!node) return false;
        }
        return true;
    }
};

Common pitfalls

• Forgetting the end-of-word marker (prefix vs word)
• In Word Search II, remove found words to avoid duplicates

Practice · 0 / 3 done

• Design Add And Search Words Data StructureMedium
• Implement Trie Prefix TreeMedium
• Word Search IIHard