Longest Word in Dictionary Using Trie in DSA C++

Mental Model

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

Analogy: Imagine a tree of building blocks where each block adds a letter. We only keep paths where every partial stack is a valid word, like building a tower with stable layers.

root
 ↓
 t -> r -> i -> e
 ↑    ↑    ↑    ↑
 w    e    e    null

Dry Run Walkthrough

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

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

Step 1: Insert 'a' into trie

root -> a[isWord=true] -> null

Why: Start building trie with first word

Step 2: Insert 'ap' into trie

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

Why: Add second word, mark prefix 'ap' as word

Step 3: Insert 'app' into trie

root -> a[true] -> p[true] -> p[true] -> null

Why: Add 'app' and mark its node as word

Step 4: Insert 'appl' into trie

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

Why: Add 'appl' and mark node as word

Step 5: Insert 'apple' into trie

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

Why: Add 'apple' and mark node as word

Step 6: Insert 'apply' into trie

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

Why: Add 'apply' and mark node as word

Step 7: Search longest word where all prefixes are words

Check 'a', 'ap', 'app', 'appl', 'apple', 'apply' all prefixes true

Why: Only words with all prefixes marked as word qualify

Step 8: Choose longest word with lex order tie-break

Longest words: 'apple' and 'apply', choose 'apple' (lex smaller)

Why: Return longest valid word with smallest lex order

Result:

apple

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct TrieNode {
    TrieNode* children[26] = {nullptr};
    bool isWord = false;
};

class Trie {
public:
    TrieNode* root;
    Trie() { root = new TrieNode(); }

    void insert(const string& word) {
        TrieNode* curr = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!curr->children[idx])
                curr->children[idx] = new TrieNode();
            curr = curr->children[idx];
        }
        curr->isWord = true;
    }

    void dfs(TrieNode* node, string& path, string& longest) {
        if (!node->isWord && node != root) return; // only continue if prefix is word

        if (path.length() > longest.length() ||
            (path.length() == longest.length() && path < longest)) {
            longest = path;
        }

        for (int i = 0; i < 26; i++) {
            if (node->children[i]) {
                path.push_back('a' + i);
                dfs(node->children[i], path, longest);
                path.pop_back();
            }
        }
    }
};

string longestWord(vector<string>& words) {
    Trie trie;
    for (const string& w : words) {
        trie.insert(w);
    }
    string longest = "";
    string path = "";
    trie.dfs(trie.root, path, longest);
    return longest;
}

int main() {
    vector<string> words = {"a", "app", "ap", "apply", "apple", "appl"};
    cout << longestWord(words) << "\n";
    return 0;
}

if (!curr->children[idx]) curr->children[idx] = new TrieNode();

create child node if missing to build trie path

curr = curr->children[idx];

advance current node to child for next letter

curr->isWord = true;

mark node as end of a valid word

if (!node->isWord && node != root) return;

stop DFS if prefix is not a word (except root)

if (path.length() > longest.length() || (path.length() == longest.length() && path < longest)) { longest = path; }

update longest word if current path is longer or lex smaller

for (int i = 0; i < 26; i++) { if (node->children[i]) { path.push_back('a' + i); dfs(node->children[i], path, longest); path.pop_back(); } }

explore all children recursively to find longest valid word

Output

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 words' letters

vs Alternative: Compared to sorting and checking prefixes in array (O(N L log N)), trie offers efficient prefix checks in O(L)

Edge Cases

empty list

returns empty string as no words exist

DSA C++

if (!node->isWord && node != root) return;

single letter words only

returns the lex smallest single letter word

DSA C++

if (path.length() > longest.length() || (path.length() == longest.length() && path < longest)) { longest = path; }

words with missing prefixes

skips words whose prefixes are not all words

DSA C++

if (!node->isWord && node != root) return;

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 prefix node is not marked as word

Mistake: Not updating longest word correctly when lengths tie
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 with lex order tie-break.