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).