Longest Word in Dictionary Using Trie in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Longest Word Found Using Trie

What is the output of the following C++ code that inserts words into a Trie and finds the longest word where all prefixes are present?

DSA C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct TrieNode {
    TrieNode* children[26] = {nullptr};
    bool isEnd = false;
};

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

    void insert(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx])
                node->children[idx] = new TrieNode();
            node = node->children[idx];
        }
        node->isEnd = true;
    }

    string longestWord() {
        string result = "";
        dfs(root, "", result);
        return result;
    }

private:
    void dfs(TrieNode* node, string current, string& result) {
        if (!node->isEnd && current != "") return;
        if (current.length() > result.length() || (current.length() == result.length() && current < result))
            result = current;
        for (int i = 0; i < 26; i++) {
            if (node->children[i]) {
                dfs(node->children[i], current + char('a' + i), result);
            }
        }
    }
};

int main() {
    vector<string> words = {"a", "banana", "app", "appl", "ap", "apply", "apple"};
    Trie trie;
    for (auto& w : words) trie.insert(w);
    cout << trie.longestWord() << endl;
    return 0;
}

A "banana"

B "apply"

C "apple"

D "app"

💡 Hint

Check which words have all their prefixes present in the dictionary.

The longest word where all prefixes are present is "apple" because "a", "ap", "app", "appl", and "apple" are all in the list. "apply" also qualifies but has the same length and is lexicographically larger than "apple". "banana" is not valid because prefixes like "b" or "ba" are missing.

🧠 Conceptual

intermediate

Why use Trie for Longest Word in Dictionary?

Why is a Trie data structure suitable for finding the longest word in a dictionary where all prefixes are present?

A Because Trie stores words in a tree structure allowing prefix checks efficiently.

B Because Trie sorts words alphabetically automatically.

C Because Trie uses hashing to find words quickly.

D Because Trie compresses words to save memory.

💡 Hint

Think about how prefix checking is done.

Trie stores words character by character in a tree, so checking if all prefixes exist is efficient by traversing nodes.

🔧 Debug

advanced

Identify the Bug in Trie Longest Word DFS

What is the bug in the following DFS function used to find the longest word in a Trie where all prefixes are present? void dfs(TrieNode* node, string current, string& result) { if (!node->isEnd && current != "") return; if (current.length() >= result.length()) result = current; for (int i = 0; i < 26; i++) { if (node->children[i]) { dfs(node->children[i], current + char('a' + i), result); } } }

A It should return immediately when node->isEnd is true.

B It does not check lexicographical order when lengths are equal, so result may not be lex smallest.

C It should not add characters to current string during recursion.

D It should use BFS instead of DFS for correct result.

💡 Hint

Check the condition when updating the result string.

The code updates result when current length is >= result length but does not check lex order if lengths are equal, so it may pick a lexicographically larger word.

❓ Predict Output

advanced

Output of Trie Longest Word with Missing Prefixes

What is the output of this code snippet that inserts words and finds the longest word with all prefixes present? Words: ["w", "wo", "wor", "worl", "world", "banana"]

DSA C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct TrieNode {
    TrieNode* children[26] = {nullptr};
    bool isEnd = false;
};

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

    void insert(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx])
                node->children[idx] = new TrieNode();
            node = node->children[idx];
        }
        node->isEnd = true;
    }

    string longestWord() {
        string result = "";
        dfs(root, "", result);
        return result;
    }

private:
    void dfs(TrieNode* node, string current, string& result) {
        if (!node->isEnd && current != "") return;
        if (current.length() > result.length() || (current.length() == result.length() && current < result))
            result = current;
        for (int i = 0; i < 26; i++) {
            if (node->children[i]) {
                dfs(node->children[i], current + char('a' + i), result);
            }
        }
    }
};

int main() {
    vector<string> words = {"w", "wo", "wor", "worl", "world", "banana"};
    Trie trie;
    for (auto& w : words) trie.insert(w);
    cout << trie.longestWord() << endl;
    return 0;
}

A "world"

B "banana"

C "worl"

D "wor"

💡 Hint

Check if all prefixes of "world" are present.

"world" is the longest word where all prefixes "w", "wo", "wor", "worl" are present. "banana" is not valid because prefixes like "b" are missing.

🚀 Application

expert

Longest Word in Dictionary Using Trie - Algorithm Complexity

What is the time complexity of finding the longest word in a dictionary using a Trie where all prefixes are present, given n words with maximum length m?

A O(n * log n) due to sorting words before insertion

B O(n^2) because each word is compared with all others

C O(m^2) because DFS explores all prefixes repeatedly

D O(n * m) for building the Trie + O(n * m) for DFS traversal, total O(n * m)

💡 Hint

Consider insertion and traversal costs separately.

Building the Trie takes O(n * m) inserting each character of each word. DFS visits each node once, also O(n * m). Total is O(n * m).

Practice

1. What is the main purpose of using a Trie data structure when finding the longest word in a dictionary?

easy

A. To sort words alphabetically

B. To reverse the words in the dictionary

C. To count the total number of words

D. To efficiently store and search words by their prefixes

Solution

1. Step 1: Understand Trie usage

   A Trie stores words by their prefixes, allowing quick prefix checks.

2. Step 2: Relate to longest word search

   Finding the longest word with all prefixes present is easier with prefix-based storage.

3. Final Answer:

   To efficiently store and search words by their prefixes -> Option D

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie stores prefixes for fast word checks [OK]

Common Mistakes:

• Thinking Trie sorts words alphabetically
• Confusing Trie with simple arrays
• Assuming Trie counts words only

2. Which of the following is the correct way to declare a Trie node class in C++ for lowercase English letters?

easy

A. class TrieNode { public: vector<TrieNode> children; bool isEnd; TrieNode() { isEnd = false; } };

B. class TrieNode { public: TrieNode* children[26]; bool isEnd; TrieNode() { for(int i=0; i<26; i++) children[i] = nullptr; isEnd = false; } };

C. class TrieNode { public: TrieNode* children[52]; bool isEnd; TrieNode() { for(int i=0; i<52; i++) children[i] = nullptr; isEnd = false; } };

D. class TrieNode { public: int children[26]; bool isEnd; TrieNode() { for(int i=0; i<26; i++) children[i] = 0; isEnd = true; } };

Solution

1. Step 1: Check children type and size

   Children should be pointers to TrieNode, size 26 for lowercase letters.

2. Step 2: Check initialization

   Initialize all children to nullptr and isEnd to false.

3. Final Answer:

   class TrieNode { public: TrieNode* children[26]; bool isEnd; TrieNode() { for(int i=0; i<26; i++) children[i] = nullptr; isEnd = false; } }; -> Option B

4. Quick Check:

   Pointer array size 26, initialized null [OK]

Hint: Use pointer array size 26 for lowercase letters [OK]

Common Mistakes:

• Using int array instead of pointers
• Wrong array size (52 instead of 26)
• Not initializing children to nullptr

3. What will be the output of the following code snippet that inserts words into a Trie and finds the longest word where all prefixes exist? vector<string> words = {"a", "ap", "app", "appl", "apple", "apply"}; // After building Trie and searching longest word cout << longestWord(words) << endl;

medium

A. "apple"

B. "apply"

C. "appl"

D. "app"

Solution

1. Step 1: Insert all words into Trie

   Words "a", "ap", "app", "appl", "apple", "apply" are inserted.

2. Step 2: Find longest word with all prefixes present

   "apple" and "apply" both have all prefixes present, but "apple" comes first lexicographically.

3. Final Answer:

   "apple" -> Option A

4. Quick Check:

   Longest word with all prefixes = "apple" [OK]

Hint: Check all prefixes exist; choose longest lex smallest [OK]

Common Mistakes:

• Choosing "apply" ignoring lex order
• Choosing shorter words like "app"
• Not verifying all prefixes exist

4. Identify the error in this Trie insertion code snippet for lowercase English letters: void insert(TrieNode* root, string word) { TrieNode* node = root; for (char c : word) { int index = c - 'a'; if (!node->children[index]) node->children[index] = new TrieNode(); node = node->children[index]; } node->isEnd = true; }

medium

A. No error; code is correct

B. Incorrect calculation of index from character

C. Missing initialization of root node before insertion

D. Not marking the end of word after insertion

Solution

1. Step 1: Check index calculation

   Index is correctly calculated as c - 'a' for lowercase letters.

2. Step 2: Verify insertion and end marking

   Children nodes are created if null, and isEnd is set true after insertion.

3. Final Answer:

   No error; code is correct -> Option A

4. Quick Check:

   Insertion logic correct [OK]

Hint: Check index and isEnd marking carefully [OK]

Common Mistakes:

• Miscomputing index for uppercase letters
• Forgetting to mark isEnd true
• Not initializing root before use (outside snippet)

5. Given a list of words, how would you modify the Trie-based approach to find the longest word where every prefix is also a valid word, but now the dictionary may contain uppercase and lowercase letters mixed? Choose the best approach.

hard

A. Ignore case and treat uppercase and lowercase as same during insertion

B. Convert all words to lowercase before inserting into Trie and searching

C. Use a Trie with 52 children per node to handle both cases distinctly

D. Use a hash map instead of Trie for faster prefix checks

Solution

1. Step 1: Understand case sensitivity

   Uppercase and lowercase letters differ; need to distinguish them in Trie.

2. Step 2: Adjust Trie structure

   Use 52 children per node (26 lowercase + 26 uppercase) to store all letters distinctly.

3. Final Answer:

   Use a Trie with 52 children per node to handle both cases distinctly -> Option C

4. Quick Check:

   Handle case by expanding Trie size [OK]

Hint: Expand Trie children to 52 for mixed case [OK]

Common Mistakes:

• Converting all to lowercase loses case info
• Ignoring case causes wrong matches
• Using hash map loses prefix tree benefits