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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trie Insertion and Longest Word Search

What is the output of the following C code that inserts words into a Trie and finds the longest word where every prefix is also a word?

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ALPHABET_SIZE 26

typedef struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    int isEndOfWord;
} TrieNode;

TrieNode* getNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->isEndOfWord = 0;
    for (int i = 0; i < ALPHABET_SIZE; i++)
        node->children[i] = NULL;
    return node;
}

void insert(TrieNode* root, const char* key) {
    TrieNode* pCrawl = root;
    for (int level = 0; key[level] != '\0'; level++) {
        int index = key[level] - 'a';
        if (!pCrawl->children[index])
            pCrawl->children[index] = getNode();
        pCrawl = pCrawl->children[index];
    }
    pCrawl->isEndOfWord = 1;
}

int isValidPrefix(TrieNode* root, const char* word, int length) {
    if (!root) return 0;
    TrieNode* pCrawl = root;
    for (int i = 0; i < length; i++) {
        int index = word[i] - 'a';
        pCrawl = pCrawl->children[index];
        if (!pCrawl || !pCrawl->isEndOfWord)
            return 0;
    }
    return 1;
}

void findLongestWordUtil(TrieNode* root, char words[][20], int n, char* longestWord) {
    for (int i = 0; i < n; i++) {
        int len = strlen(words[i]);
        if (len > strlen(longestWord) && isValidPrefix(root, words[i], len)) {
            strcpy(longestWord, words[i]);
        }
    }
}

int main() {
    char words[][20] = {"a", "app", "ap", "apply", "apple"};
    int n = sizeof(words) / sizeof(words[0]);
    TrieNode* root = getNode();
    for (int i = 0; i < n; i++) {
        insert(root, words[i]);
    }
    char longestWord[20] = "";
    findLongestWordUtil(root, words, n, longestWord);
    printf("%s\n", longestWord);
    return 0;
}

A "apple"

B "apply"

C "ap"

D "app"

💡 Hint

Check which word has all prefixes present as words in the Trie and is the longest.

The code inserts all words into the Trie. Then it checks each word to see if all its prefixes are present as words (isEndOfWord == 1). Among these, it picks the longest word. "apple" and "apply" fail because the prefix "appl" is not a word. "app" has prefixes "a", "ap", "app" all present. Thus, the output is "app".

🧠 Conceptual

intermediate

Understanding Trie Node Structure

Which of the following best describes the purpose of the 'isEndOfWord' flag in a Trie node when finding the longest word in a dictionary?

A It marks the node as the end of a valid word in the dictionary.

B It counts how many words pass through this node.

C It stores the character value of the node.

D It points to the parent node in the Trie.

💡 Hint

Think about how the Trie knows when a word ends.

The 'isEndOfWord' flag is set to 1 when a node represents the last character of a valid word. This helps in identifying complete words during traversal.

🔧 Debug

advanced

Identify the Bug in Longest Word Search

Given the following snippet from a Trie-based longest word finder, what is the bug that causes incorrect results? int isValidPrefix(TrieNode* root, const char* word, int length) { TrieNode* pCrawl = root; for (int i = 0; i < length; i++) { int index = word[i] - 'a'; pCrawl = pCrawl->children[index]; if (!pCrawl || !pCrawl->isEndOfWord) return 0; } return 1; } The function is used to check if all prefixes of 'word' are valid words in the Trie.

A It incorrectly checks the full word's last character as a prefix, which should be excluded.

B It does not check if the root is NULL before traversal.

C It uses the wrong index calculation for children array.

D It should return 0 if any child node exists, not if isEndOfWord is false.

💡 Hint

Consider what prefixes mean compared to the full word.

The function does not check if root is NULL. If root is NULL, the first access pCrawl->children[index] dereferences NULL, causing a segmentation fault.

🚀 Application

advanced

Longest Word with All Prefixes Present

You have a list of words: ["w", "wo", "wor", "worl", "world", "word", "worst"]. Using a Trie, which word will be identified as the longest word where every prefix is also a word?

A "worst"

B "word"

C "world"

D "worl"

💡 Hint

Check each word's prefixes and see if all are present in the list.

"world" has prefixes "w", "wo", "wor", "worl" all present in the list. "worst" fails because "wors" is not in the list. "word" is valid but shorter than "world". "worl" is shorter than "world". So "world" is the longest valid word.

🧠 Conceptual

expert

Why Use Trie for Longest Word in Dictionary?

Why is a Trie data structure preferred over a hash set for finding the longest word in a dictionary where every prefix is also a word?

A Trie allows efficient prefix checks by traversing nodes, while hash sets require repeated substring lookups.

B Trie uses less memory than hash sets for storing words.

C Hash sets cannot store strings, only integers.

D Trie automatically sorts words lexicographically, hash sets do not.

💡 Hint

Think about how prefix checking is done in both data structures.

Trie stores words in a tree structure where each node represents a character, making prefix checks fast by traversing nodes. Hash sets require checking each prefix substring separately, which is less efficient.

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 count the total number of words

C. To efficiently store and search words by their prefixes

D. To reverse the words in the dictionary

Solution

1. Step 1: Understand Trie usage

   A Trie stores words by breaking them into characters and linking nodes for prefixes.

2. Step 2: Relate to longest word search

   This structure allows quick prefix checks, which helps find the longest word built from other words.

3. Final Answer:

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

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is best for prefix-based word searches [OK]

Common Mistakes:

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

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

easy

A. typedef struct TrieNode { struct TrieNode* children[26]; int isEndOfWord; } TrieNode;

B. typedef struct TrieNode { struct TrieNode* children[52]; int isEndOfWord; } TrieNode;

C. typedef struct TrieNode { struct TrieNode* children[10]; int isEndOfWord; } TrieNode;

D. typedef struct TrieNode { struct TrieNode* children; int isEndOfWord; } TrieNode;

Solution

1. Step 1: Identify children array size

   Lowercase English letters are 26, so children array size must be 26.

2. Step 2: Check structure fields

   Each node has an array of pointers and a flag for word end, matching typedef struct TrieNode { struct TrieNode* children[26]; int isEndOfWord; } TrieNode;.

3. Final Answer:

   typedef struct TrieNode { struct TrieNode* children[26]; int isEndOfWord; } TrieNode; -> Option A

4. Quick Check:

   26 children for a-z [OK]

Hint: Use 26 children for lowercase letters [OK]

Common Mistakes:

• Using 52 for uppercase + lowercase without need
• Using 10 children for digits only
• Not using array for children pointers

3. Given the following code snippet inserting words into a Trie and searching for the longest word built one character at a time, what will be the output?

char* words[] = {"a", "ap", "app", "appl", "apple", "apply"};
// Assume insert and search functions are correct
// Function finds longest word where all prefixes exist
printf("%s", longestWord(words, 6));

medium

A. apple

B. apply

C. appl

D. app

Solution

1. Step 1: Check all prefixes for each word

   Words like "apple" and "apply" have all prefixes present: a, ap, app, appl.

2. Step 2: Compare lengths of valid words

   "apple" and "apply" both have length 5, but "apple" comes first lexicographically.

3. Final Answer:

   apple -> Option A

4. Quick Check:

   Longest valid word = apple [OK]

Hint: Check all prefixes exist, pick longest lex order first [OK]

Common Mistakes:

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

4. The following code tries to find the longest word in a dictionary using a Trie but always returns an empty string. What is the bug?

void insert(TrieNode* root, char* word) {
    TrieNode* node = root;
    for (int i = 0; word[i]; i++) {
        int index = word[i] - 'a';
        if (!node->children[index])
            node->children[index] = createNode();
        node = node->children[index];
    }
    node->isEndOfWord = 1;
}

char* longestWord(char** words, int n) {
    TrieNode* root = createNode();
    for (int i = 0; i < n; i++)
        insert(root, words[i]);
    // Missing code to find longest word
    return "";
}

medium

A. The children array size is incorrect

B. The longestWord function does not search the Trie for the longest word

C. The insert function does not mark end of word correctly

D. The root node is not initialized

Solution

1. Step 1: Analyze insert function

   Insert correctly adds words and marks end of word, so no issue here.

2. Step 2: Check longestWord function

   It inserts words but returns empty string without searching Trie for longest word.

3. Final Answer:

   The longestWord function does not search the Trie for the longest word -> Option B

4. Quick Check:

   Missing search logic causes empty output [OK]

Hint: Check if search logic exists after insertion [OK]

Common Mistakes:

• Assuming insert alone finds longest word
• Ignoring missing traversal in longestWord
• Thinking root node is uninitialized

5. You want to find the longest word in a dictionary such that every prefix of the word is also a word in the dictionary. Which approach using a Trie is best to solve this efficiently?

hard

A. Use BFS on Trie without checking end of word flags

B. Sort words by length, then check each word's prefixes in a hash set

C. Insert words into Trie and count total nodes to find longest word

D. Insert all words into Trie, then do DFS checking only nodes marking end of words to build longest word

Solution

1. Step 1: Insert all words into Trie

   Build Trie with all dictionary words, marking end of word nodes.

2. Step 2: Use DFS to find longest word

   Traverse Trie depth-first, only continuing on nodes that mark end of words to ensure all prefixes exist.

3. Step 3: Track longest word during traversal

   Keep updating longest word found by length and lex order during DFS.

4. Final Answer:

   Insert all words into Trie, then do DFS checking only nodes marking end of words to build longest word -> Option D

5. Quick Check:

   Trie + DFS + endOfWord check = longest word [OK]

Hint: Use DFS on Trie nodes with endOfWord true only [OK]

Common Mistakes:

• Ignoring prefix checks during traversal
• Using BFS without endOfWord validation
• Relying on sorting without Trie