Longest Word in Dictionary Using Trie in DSA C - Build from Scratch

Longest Word in Dictionary Using Trie

📖 Scenario: Imagine you have a list of words from a dictionary. You want to find the longest word that can be built one character at a time by other words in the list. For example, if the word is "apple", then "a", "ap", "app", "appl" must also be in the list.

🎯 Goal: Build a program in C that uses a Trie data structure to find the longest word in the dictionary that can be built character by character from other words in the dictionary.

📋 What You'll Learn

Create a Trie node structure with 26 children pointers and a boolean to mark end of word

Insert all words from the given list into the Trie

Use a helper variable to track the longest word found

Traverse the Trie to find the longest word where all prefixes are valid words

Print the longest word found

💡 Why This Matters

🌍 Real World

Tries are used in autocomplete systems, spell checkers, and word games to quickly find words and prefixes.

💼 Career

Understanding Tries and string searching algorithms is important for software engineers working on search engines, text processing, and data compression.

1

Create Trie Node Structure and Insert Words

Create a struct called TrieNode with an array of 26 TrieNode* called children and a boolean isEndOfWord. Then create a function getNode() that returns a new TrieNode with all children set to NULL and isEndOfWord set to false. Finally, create a function insert() that takes a TrieNode* root and a char* word and inserts the word into the Trie.

DSA C

# Define TrieNode struct
// Create getNode() function
// Create insert() function

Hint

Think of the TrieNode as a tree node with 26 branches for each letter. The insert function walks through the word and creates nodes as needed.

2

Setup Words Array and Root Trie Node

Create a char* array called words with these exact words: "a", "app", "ap", "apply", "apple". Then create a TrieNode* variable called root and set it to the result of getNode().

DSA C

#include 
#include 
#include 
#include 

typedef struct TrieNode {
    struct TrieNode* children[26];
    bool isEndOfWord;
} TrieNode;

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

void insert(TrieNode* root, char* word) {
    TrieNode* pCrawl = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int index = word[i] - 'a';
        if (pCrawl->children[index] == NULL) {
            pCrawl->children[index] = getNode();
        }
        pCrawl = pCrawl->children[index];
    }
    pCrawl->isEndOfWord = true;
}

// Create words array and root node below
// Your code here

Hint

Think of words as the dictionary list and root as the starting point of your Trie.

3

Insert Words and Find Longest Word

Inside main(), use a for loop with variable i to insert each word from words into the Trie using insert(root, words[i]). Then create a global char array longestWord[100] initialized to empty string. Write a recursive function dfs() that takes a TrieNode* node, a char* currentWord, and an int length. It should explore children nodes only if isEndOfWord is true, build words character by character, and update longestWord if a longer valid word is found. Call dfs(root, currentWord, 0) from main().

DSA C

#include 
#include 
#include 
#include 

typedef struct TrieNode {
    struct TrieNode* children[26];
    bool isEndOfWord;
} TrieNode;

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

void insert(TrieNode* root, char* word) {
    TrieNode* pCrawl = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int index = word[i] - 'a';
        if (pCrawl->children[index] == NULL) {
            pCrawl->children[index] = getNode();
        }
        pCrawl = pCrawl->children[index];
    }
    pCrawl->isEndOfWord = true;
}

char* words[] = {"a", "app", "ap", "apply", "apple"};
TrieNode* root = NULL;
char longestWord[100] = "";

void dfs(TrieNode* node, char* currentWord, int length) {
    // Your code here
}

int main() {
    root = getNode();
    for (int i = 0; i < 5; i++) {
        insert(root, words[i]);
    }
    char currentWord[100];
    dfs(root, currentWord, 0);
    return 0;
}

Hint

Use depth-first search to explore all valid words. Only continue if the current node marks the end of a word. Update longestWord when you find a longer valid word.

4

Print the Longest Word Found

Add a printf statement in main() after calling dfs() to print the longest word found in the format: Longest word: %s\n using the variable longestWord.

DSA C

#include 
#include 
#include 
#include 

typedef struct TrieNode {
    struct TrieNode* children[26];
    bool isEndOfWord;
} TrieNode;

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

void insert(TrieNode* root, char* word) {
    TrieNode* pCrawl = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int index = word[i] - 'a';
        if (pCrawl->children[index] == NULL) {
            pCrawl->children[index] = getNode();
        }
        pCrawl = pCrawl->children[index];
    }
    pCrawl->isEndOfWord = true;
}

char* words[] = {"a", "app", "ap", "apply", "apple"};
TrieNode* root = NULL;
char longestWord[100] = "";

void dfs(TrieNode* node, char* currentWord, int length) {
    if (node == NULL) return;
    if (node != root && node->isEndOfWord == false) return;

    if (length > 0) {
        currentWord[length] = '\0';
        if (strlen(currentWord) > strlen(longestWord) ||
            (strlen(currentWord) == strlen(longestWord) && strcmp(currentWord, longestWord) children[i] != NULL) {
            currentWord[length] = 'a' + i;
            dfs(node->children[i], currentWord, length + 1);
        }
    }
}

int main() {
    root = getNode();
    for (int i = 0; i < 5; i++) {
        insert(root, words[i]);
    }
    char currentWord[100];
    dfs(root, currentWord, 0);
    // Print the longest word below
    // Your code here
    return 0;
}

Hint

Use printf("Longest word: %s\n", longestWord); to show the result.

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