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 "a", "ap", "app", "appl", and "apple" are in the list, "apple" is the longest word that can be built step by step.

🎯 Goal: You will build a program using a Trie data structure to find the longest word in a list where every prefix of the word is also in the list.

📋 What You'll Learn

Create a TrieNode class with children and end-of-word marker

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 exist

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 search algorithms is important for software engineering roles involving text processing, search engines, and data indexing.

1

Create TrieNode class and insert words

Create a class called TrieNode with a public array children of size 26 initialized to nullptr and a boolean isEnd initialized to false. Then create a class called Trie with a public root node of type TrieNode*. Add a public method insert that takes a string word and inserts it into the Trie. Finally, create a vector of strings called words with these exact values: "w", "wo", "wor", "worl", "world" and insert each word into the Trie using the insert method.

DSA C++

# Your code here

Hint

Remember to initialize all children pointers to nullptr and set isEnd to false in the TrieNode constructor. Insert each word character by character.

2

Add helper variable to track longest word

Add a global string variable called longestWord initialized to an empty string "" to keep track of the longest valid word found so far.

DSA C++

#include 
#include 
#include 
using namespace std;

class TrieNode {
public:
    TrieNode* children[26];
    bool isEnd;
    TrieNode() {
        for (int i = 0; i children[index]) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->isEnd = true;
    }
};

vector words = {"w", "wo", "wor", "worl", "world"};
Trie trie;

string longestWord = "";  // Your code here

int main() {
    for (string word : words) {
        trie.insert(word);
    }
    // Your code here
    return 0;
}

Hint

Declare longestWord outside main() so it can be used in other functions later.

3

Traverse Trie to find longest valid word

Add a recursive function called dfs that takes a TrieNode* called node and a string currentWord. The function should check if node->isEnd is true or if node is the root. If not, return immediately. If currentWord is longer than longestWord or equal length but lexicographically smaller, update longestWord. Then for each child from 'a' to 'z', if the child exists, call dfs recursively with the child node and currentWord plus the child's character. Call dfs from main starting with trie.root and empty string "".

DSA C++

#include 
#include 
#include 
using namespace std;

class TrieNode {
public:
    TrieNode* children[26];
    bool isEnd;
    TrieNode() {
        for (int i = 0; i children[index]) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->isEnd = true;
    }
};

vector words = {"w", "wo", "wor", "worl", "world"};
Trie trie;

string longestWord = "";

void dfs(TrieNode* node, string currentWord) {
    // Your code here
}

int main() {
    for (string word : words) {
        trie.insert(word);
    }
    dfs(trie.root, "");
    return 0;
}

Hint

Check if the current node is the root or marks the end of a word before continuing. Update longestWord if the current word is longer or lexicographically smaller when lengths are equal.

4

Print the longest word found

Add a cout statement in main to print the value of longestWord.

DSA C++

#include 
#include 
#include 
using namespace std;

class TrieNode {
public:
    TrieNode* children[26];
    bool isEnd;
    TrieNode() {
        for (int i = 0; i children[index]) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->isEnd = true;
    }
};

vector words = {"w", "wo", "wor", "worl", "world"};
Trie trie;

string longestWord = "";

void dfs(TrieNode* node, string currentWord) {
    if (node != trie.root && !node->isEnd) {
        return;
    }
    if (currentWord.length() > longestWord.length() ||
        (currentWord.length() == longestWord.length() && currentWord children[i]) {
            dfs(node->children[i], currentWord + char('a' + i));
        }
    }
}

int main() {
    for (string word : words) {
        trie.insert(word);
    }
    dfs(trie.root, "");
    cout << longestWord << endl;  // Your code here
    return 0;
}

Hint

Use cout << longestWord << endl; to print the longest word after the DFS completes.