Longest Word in Dictionary Using Trie in DSA C

Mental Model

Build a tree where each path from root to a node forms a prefix of words. Then find the longest word where every prefix is also a word.

Analogy: Imagine a family tree where each generation adds one letter. We want the longest name where every smaller name before it is also in the family.

root
 ↓
 a -> p -> p -> l -> e
       ↓
       e -> null
Each arrow is a letter link forming words like 'app' and 'apple'.

Dry Run Walkthrough

Input: words: ["a", "app", "apple", "apply", "ap", "appl"]

Goal: Find the longest word where all prefixes are also words in the list

Step 1: Insert 'a' into trie

root -> a[isWord=true]

Why: Start building trie with first word

Step 2: Insert 'app' into trie

root -> a[isWord=true] -> p[isWord=false] -> p[isWord=true]

Why: Add letters and mark end of word

Step 3: Insert 'apple' into trie

root -> a[true] -> p[false] -> p[true] -> l[false] -> e[true]

Why: Add new letters for 'apple' and mark end

Step 4: Insert 'apply' into trie

root -> a[true] -> p[false] -> p[true] -> l[false] -> y[true]

Why: Add 'y' node for 'apply' word

Step 5: Insert 'ap' into trie

root -> a[true] -> p[true] -> p[true] -> l[false] -> e[true]

Why: Mark 'p' node as word end for 'ap'

Step 6: Insert 'appl' into trie

root -> a[true] -> p[true] -> p[true] -> l[true] -> e[true]

Why: Mark 'l' node as word end for 'appl'

Step 7: Search longest word where all prefixes are words

Check 'a', 'ap', 'app', 'appl', 'apple', 'apply'

Why: Only words with all prefixes marked as words qualify

Step 8: Find 'apple' and 'apply' both valid, choose lex smaller 'apple'

Longest word: 'apple'

Why: Both have all prefixes, 'apple' is lex smaller

Result:

Longest word in trie: apple

Annotated Code

DSA C

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

#define ALPHABET_SIZE 26

// Trie node structure
typedef struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    bool isWord;
} TrieNode;

// Create a new trie node
TrieNode* getNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->isWord = false;
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        node->children[i] = NULL;
    }
    return node;
}

// Insert a word into trie
void insert(TrieNode* root, const char* word) {
    TrieNode* curr = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int index = word[i] - 'a';
        if (!curr->children[index]) {
            curr->children[index] = getNode();
        }
        curr = curr->children[index];
    }
    curr->isWord = true;
}

// Helper function to find longest word with all prefixes present
void dfs(TrieNode* root, char* path, int depth, char* longest) {
    // If current node is not a word and not root, stop
    if (root != NULL && root->isWord == false && depth != 0) return;

    // Terminate current path string
    path[depth] = '\0';

    // Update longest if current path is longer or lex smaller if same length
    if (depth > 0) {
        if (strlen(longest) < depth || (strlen(longest) == depth && strcmp(path, longest) < 0)) {
            strcpy(longest, path);
        }
    }

    // Explore children
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (root->children[i]) {
            path[depth] = 'a' + i;
            dfs(root->children[i], path, depth + 1, longest);
        }
    }
}

int main() {
    const char* words[] = {"a", "app", "apple", "apply", "ap", "appl"};
    int n = sizeof(words) / sizeof(words[0]);

    TrieNode* root = getNode();

    // Insert all words
    for (int i = 0; i < n; i++) {
        insert(root, words[i]);
    }

    char path[1000];
    char longest[1000] = "";

    dfs(root, path, 0, longest);

    printf("Longest word in trie: %s\n", longest);

    return 0;
}

for (int i = 0; word[i] != '\0'; i++) {

Traverse each letter to insert nodes

if (!curr->children[index]) { curr->children[index] = getNode(); }

Create new node if letter path missing

curr->isWord = true;

Mark end of inserted word

if (root != NULL && root->isWord == false && depth != 0) return;

Stop DFS if current prefix is not a word

if (strlen(longest) < depth || (strlen(longest) == depth && strcmp(path, longest) < 0)) { strcpy(longest, path); }

Update longest word if current path is longer or lex smaller

for (int i = 0; i < ALPHABET_SIZE; i++) { if (root->children[i]) { dfs(root->children[i], path, depth + 1, longest); } }

Recursively explore all children nodes

Output

Longest word in trie: apple

Complexity Analysis

Time: O(N * L) because we insert N words each of length L and DFS visits nodes once

Space: O(N * L) for trie nodes storing all letters of all words

vs Alternative: Compared to checking prefixes in a hash set for each word (O(N * L^2)), trie is more efficient for prefix checks

Edge Cases

Empty list of words

Returns empty string as no words exist

DSA C

if (root != NULL && root->isWord == false && depth != 0) return;

Words with single letter only

Returns the longest single letter word present

DSA C

curr->isWord = true;

Multiple longest words with same length

Returns lexicographically smallest word

DSA C

if (strlen(longest) < depth || (strlen(longest) == depth && strcmp(path, longest) < 0)) { strcpy(longest, path); }

When to Use This Pattern

When asked to find the longest word with all prefixes present, use a trie to efficiently check prefixes and find the answer by DFS.

Common Mistakes

Mistake: Not checking if all prefixes are words before continuing DFS
Fix: Add condition to stop DFS if current node is not marked as word

Mistake: Updating longest word without lexicographical comparison
Fix: Compare lex order when lengths are equal to pick smallest word

Summary

Build a trie from words and find the longest word where every prefix is also a word.

Use when you need to find words with all prefixes present efficiently.

The key is to stop exploring paths where prefixes are missing and track longest valid word.

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