Skip to content
DSA tries 14 min read

Trie Exercises: Answer Sheet & Worked Solutions

This is the answer sheet for the trie exercises. Each solution gives the key idea, the optimal complexity, the code in all four languages (use the switcher), and common pitfalls. Throughout, L is the length of a word or prefix and n is the number of stored words. Try the problems first — then check your work here.

Idea: Store a TrieNode with a children map and an isEnd flag. insert walks the word, creating missing nodes, and sets isEnd on the last node. search walks the word and checks isEnd; startsWith only checks that the path exists.

Complexity: O(L) time per operation, O(1) extra space (insert allocates up to L new nodes).

class Trie {
    struct Node {
        std::unordered_map<char, Node*> children;
        bool isEnd = false;
    };
    Node* root = new Node();
    Node* walk(const std::string& s) {
        Node* node = root;
        for (char ch : s) {
            auto it = node->children.find(ch);
            if (it == node->children.end()) return nullptr;
            node = it->second;
        }
        return node;
    }
public:
    void insert(const std::string& word) {
        Node* node = root;
        for (char ch : word) {
            if (!node->children.count(ch)) node->children[ch] = new Node();
            node = node->children[ch];
        }
        node->isEnd = true;
    }
    bool search(const std::string& word) {
        Node* node = walk(word);
        return node != nullptr && node->isEnd;
    }
    bool startsWith(const std::string& prefix) {
        return walk(prefix) != nullptr;
    }
};

Pitfall: Returning true from search just because the path exists is the classic bug. If only card was inserted, search("car") must be false — always check isEnd.

Q2. Count words and count prefixes

Idea: Augment each node with two counters: prefixCount (how many inserted words pass through this node) and wordCount (how many words end exactly here). insert bumps prefixCount on every node it visits and wordCount on the last. The two queries are just a walk returning the relevant counter.

Complexity: O(L) per operation, O(1) extra space per query.

class WordTrie {
    struct Node {
        std::unordered_map<char, Node*> children;
        int wordCount = 0;    // words ending here
        int prefixCount = 0;  // words passing through
    };
    Node* root = new Node();
    Node* walk(const std::string& s) {
        Node* node = root;
        for (char ch : s) {
            auto it = node->children.find(ch);
            if (it == node->children.end()) return nullptr;
            node = it->second;
        }
        return node;
    }
public:
    void insert(const std::string& w) {
        Node* node = root;
        for (char ch : w) {
            if (!node->children.count(ch)) node->children[ch] = new Node();
            node = node->children[ch];
            node->prefixCount++;
        }
        node->wordCount++;
    }
    int countWordsEqualTo(const std::string& w) {
        Node* n = walk(w);
        return n ? n->wordCount : 0;
    }
    int countWordsStartingWith(const std::string& p) {
        Node* n = walk(p);
        return n ? n->prefixCount : 0;
    }
};

Pitfall: Incrementing prefixCount on the root makes “words starting with empty string” wrong relative to other prefixes. Increment only on nodes you step into, never the root.

Q3. Delete a word from a trie

Idea: Recurse to the end of the word. Unset isEnd; then on the way back up, prune a child only if it has no other children and is not itself a word end. The recursion returns “should my parent delete me?” to drive the pruning. Add this to the Trie from Q1.

Complexity: O(L) time, O(L) recursion stack.

// returns true if `node` can be removed by its parent
bool removeHelper(Node* node, const std::string& word, int i) {
    if (i == (int)word.size()) {
        if (!node->isEnd) return false;     // word not present
        node->isEnd = false;
        return node->children.empty();      // prune if it is now a leaf
    }
    char ch = word[i];
    auto it = node->children.find(ch);
    if (it == node->children.end()) return false;
    if (removeHelper(it->second, word, i + 1)) {
        delete it->second;
        node->children.erase(it);
        return !node->isEnd && node->children.empty();
    }
    return false;
}
void remove(const std::string& word) { removeHelper(root, word, 0); }

Pitfall: Deleting nodes unconditionally destroys shared prefixes. If card and car both exist, deleting car must only flip its isEnd flag — the car path is still needed by card. Only prune leaves with no isEnd.

Q4. Autocomplete — all words with a prefix

Idea: Walk to the prefix node, then DFS its subtree, rebuilding each word and collecting nodes with isEnd. Iterating children in sorted order yields suggestions alphabetically.

Complexity: O(L + k) time, where k is the size of the matched subtree; O(k) for the output.

class Autocomplete {
    struct Node {
        std::map<char, Node*> children;   // ordered -> sorted suggestions
        bool isEnd = false;
    };
    Node* root = new Node();
    void collect(Node* node, std::string& path, std::vector<std::string>& out) {
        if (node->isEnd) out.push_back(path);
        for (auto& [ch, child] : node->children) {
            path.push_back(ch);
            collect(child, path, out);
            path.pop_back();
        }
    }
public:
    void insert(const std::string& word) {
        Node* node = root;
        for (char ch : word) {
            if (!node->children.count(ch)) node->children[ch] = new Node();
            node = node->children[ch];
        }
        node->isEnd = true;
    }
    std::vector<std::string> suggest(const std::string& prefix) {
        std::vector<std::string> out;
        Node* node = root;
        for (char ch : prefix) {
            auto it = node->children.find(ch);
            if (it == node->children.end()) return out;
            node = it->second;
        }
        std::string path = prefix;
        collect(node, path, out);
        return out;
    }
};

Pitfall: If the prefix path does not exist, return an empty list — do not start collecting from the root, which would dump the entire dictionary.

Q5. Longest common prefix of a set of words

Idea: Insert all words into a trie, then walk down from the root as long as the current node has exactly one child and is not itself a word end. The characters you pass form the longest common prefix.

Complexity: O(total characters) to build, O(answer length) to walk.

std::string longestCommonPrefix(const std::vector<std::string>& words) {
    if (words.empty()) return "";
    struct Node { std::unordered_map<char, Node*> children; bool isEnd = false; };
    Node* root = new Node();
    for (const auto& w : words) {
        Node* node = root;
        for (char ch : w) {
            if (!node->children.count(ch)) node->children[ch] = new Node();
            node = node->children[ch];
        }
        node->isEnd = true;
    }
    std::string lcp;
    Node* node = root;
    while (node->children.size() == 1 && !node->isEnd) {
        auto it = node->children.begin();
        lcp += it->first;
        node = it->second;
    }
    return lcp;
}

Pitfall: Forgetting the isEnd check makes the prefix run past a complete shorter word — e.g. for ["car", "card"] the LCP is "car", not "card". Stop at any word end.

Q6. Wildcard search with .

Idea: Insert words normally. For search, recurse character by character: a normal character follows the single matching child; a . tries every child. Success means reaching the word’s end with isEnd set.

Complexity: Normal queries are O(L). With d dots the worst case is roughly O(branching^d · L); for a query of all dots it visits every node, so O(N) where N is the number of trie nodes.

class WordDictionary {
    struct Node {
        std::unordered_map<char, Node*> children;
        bool isEnd = false;
    };
    Node* root = new Node();
    bool dfs(Node* node, const std::string& word, int i) {
        if (i == (int)word.size()) return node->isEnd;
        char ch = word[i];
        if (ch == '.') {
            for (auto& [c, child] : node->children)
                if (dfs(child, word, i + 1)) return true;
            return false;
        }
        auto it = node->children.find(ch);
        if (it == node->children.end()) return false;
        return dfs(it->second, word, i + 1);
    }
public:
    void addWord(const std::string& word) {
        Node* node = root;
        for (char ch : word) {
            if (!node->children.count(ch)) node->children[ch] = new Node();
            node = node->children[ch];
        }
        node->isEnd = true;
    }
    bool search(const std::string& word) { return dfs(root, word, 0); }
};

Pitfall: On a ., iterate the children only — never the end-of-word marker — and remember the dot consumes exactly one character. Treating . as “zero or more” turns this into a different (regex) problem.

Q7. Word search in a grid

Idea: Build a trie of all target words, storing the full word at each end node. Run a DFS from every cell, descending the board and the trie together. When the current trie node holds a word, record it (and clear it to avoid duplicates). Mark visited cells during the path and restore them on backtrack. The trie prunes any direction whose prefix is not in the dictionary.

Complexity: O(W·L) to build the trie over W words, and O(R·C·4^maxLen) worst case for the search over an R×C board, heavily pruned in practice.

struct TNode {
    std::unordered_map<char, TNode*> children;
    std::string word;   // non-empty marks a complete word
};
class Solution {
    TNode* root = new TNode();
    std::vector<std::string> result;
    void insert(const std::string& w) {
        TNode* node = root;
        for (char ch : w) {
            if (!node->children.count(ch)) node->children[ch] = new TNode();
            node = node->children[ch];
        }
        node->word = w;
    }
    void dfs(std::vector<std::vector<char>>& b, int r, int c, TNode* node) {
        if (r < 0 || c < 0 || r >= (int)b.size() || c >= (int)b[0].size()) return;
        char ch = b[r][c];
        if (ch == '#') return;
        auto it = node->children.find(ch);
        if (it == node->children.end()) return;
        TNode* next = it->second;
        if (!next->word.empty()) {
            result.push_back(next->word);
            next->word.clear();           // dedupe
        }
        b[r][c] = '#';                    // mark visited
        dfs(b, r + 1, c, next);
        dfs(b, r - 1, c, next);
        dfs(b, r, c + 1, next);
        dfs(b, r, c - 1, next);
        b[r][c] = ch;                     // restore
    }
public:
    std::vector<std::string> findWords(std::vector<std::vector<char>>& board,
                                       std::vector<std::string>& words) {
        for (auto& w : words) insert(w);
        for (int r = 0; r < (int)board.size(); r++)
            for (int c = 0; c < (int)board[0].size(); c++)
                dfs(board, r, c, root);
        return result;
    }
};

Pitfall: Forgetting to mark and restore the visited cell lets a path reuse the same letter, producing words the board cannot actually spell. Always set the cell to a sentinel before recursing and restore it after.

That’s the full answer sheet. Back to the trie exercises, revisit trie applications, or continue to graphs.

Last updated June 25, 2026
Was this helpful?