Trie bug hunt

Questions 1 to 5 of 8

1. 1. A student writes this insert for lowercase words. What goes wrong? ``cpp void insert(const std::string& word) { TrieNode* node = root_.get(); for (char c : word) { int idx = c - 'A'; auto& next = node->children.at(idx); if (!next) next = std::make_unique<TrieNode>(); node = next.get(); } node->is_end = true; } ``

   The slot should be c - 'A' + 1, so that the root keeps slot 0std::array cannot be indexed with at(), so the code does not compileThe base is 'A' (code 65), so the letter t gives index 51, and at() throws out_of_range because there are only 26 slotsThe code compiles and runs, but silently stores every word in slots 65 to 90
2. 2. This version of insert is meant to mark the end of each word. What goes wrong? ``cpp void insert(const std::string& word) { TrieNode* node = root_.get(); for (char c : word) { auto& next = node->children[c - 'a']; if (!next) { next = std::make_unique<TrieNode>(); if (c == word.back()) next->is_end = true; } node = next.get(); } } ``

   The flag is set only when a node is created, so inserting te after tea leaves the existing e node unmarked, and c == word.back() marks a middle letter that matches the last letterThe loop should stop one letter early, so the last letter is never insertedstd::array cannot hold std::unique_ptr, so the children array does not compilemake_unique should be replaced with new, because the unique_ptr would leak memory
3. 3. This search crashes on some words that are not in the trie. What is the bug? ``cpp bool search(const std::string& word) const { const TrieNode* node = root_.get(); for (char c : word) { node = node->children.at(c - 'a').get(); } return node->is_end; } ``

   The index should be c - 'A', to match the insert functionis_end must be read before the loop, because the loop changes itThe function should not be const, because it changes nodeWhen a word path reaches an empty slot, node becomes nullptr, and the next letter or the final return reads through it. The fix is to return false inside the loop when node is null
4. 4. This search gives true for words that were never inserted. What is the bug? ``cpp bool search(const std::string& word) const { const TrieNode* node = root_.get(); for (char c : word) { const TrieNode* next = node->children[c - 'a'].get(); if (next == nullptr) return false; node = next; } return node != nullptr; } ``

   The null check inside the loop should be removed, because nullptr is never a valid nodeThe last line checks whether the node exists, not whether a word ends there. After inserting cat, a search for ca returns true because the node for a exists, so the last line should be return node->is_endThe loop reads one letter too few, so the last node is skippedThe function should return true only when word is the empty string
5. 5. What does this program print? ``cpp #include <iostream> #include <string> using namespace std; int main() { string word = "tea"; for (char c : word) { cout << (c - 'a') << (c == word.back() ? '\n' : ','); } } ``

   0,4,1919,4,0116,101,9720,5,1