Longest Word in Dictionary Using Trie in DSA Javascript

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 family tree where each generation adds a letter. We want the longest name where every smaller name before it is also in the family.

root
 ↓
 t -> r -> i -> e
 ↑
 start

Dry Run Walkthrough

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

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

Step 1: Insert 'a' into the trie

root -> a* (end of word)
 ↑

Why: We add the first word and mark its end

Step 2: Insert 'ap' into the trie

root -> a* -> p* (end of word)
 ↑

Why: Add second word, mark end at 'p'

Step 3: Insert 'app' into the trie

root -> a* -> p* -> p* (end of word)
 ↑

Why: Add third word, mark end at second 'p'

Step 4: Insert 'appl' into the trie

root -> a* -> p* -> p* -> l* (end of word)
 ↑

Why: Add fourth word, mark end at 'l'

Step 5: Insert 'apple' into the trie

root -> a* -> p* -> p* -> l* -> e* (end of word)
 ↑

Why: Add fifth word, mark end at 'e'

Step 6: Insert 'apply' into the trie

root -> a* -> p* -> p* -> l* -> y* (end of word)
 ↑

Why: Add sixth word, mark end at 'y'

Step 7: Search for longest word where all prefixes are words

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

Why: We verify each prefix is a word to find the longest valid word

Step 8: Choose 'apple' as longest valid word

Longest word: apple

Why: All prefixes of 'apple' exist as words. 'apply' also qualifies (all prefixes including 'appl' are words), but 'apple' is lexicographically smaller

Result:

root -> a* -> p* -> p* -> l* -> e* (apple)
Longest word: apple

Annotated Code

DSA Javascript

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char);
    }
    node.isWord = true;
  }

  longestWord() {
    let result = "";
    const dfs = (node, path) => {
      if (node !== this.root && !node.isWord) return;
      if (path.length > result.length || (path.length === result.length && path < result)) {
        result = path;
      }
      for (const [char, child] of [...node.children.entries()].sort((a, b) => a[0].localeCompare(b[0]))) {
        dfs(child, path + char);
      }
    };
    dfs(this.root, "");
    return result;
  }
}

const words = ["a", "app", "ap", "apply", "apple", "appl"];
const trie = new Trie();
for (const word of words) {
  trie.insert(word);
}
console.log(trie.longestWord());

if (!node.children.has(char)) { node.children.set(char, new TrieNode()); }

Create new child node if character path does not exist

node = node.children.get(char);

Advance node pointer to child node for current character

node.isWord = true;

Mark current node as end of a valid word

if (node !== this.root && !node.isWord) return;

Stop DFS if current node is not root and not end of a word (prefix invalid)

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

Update longest word if current path is longer or lex smaller if equal length

for (const [char, child] of [...node.children.entries()].sort((a, b) => a[0].localeCompare(b[0]))) { dfs(child, path + char); }

Traverse children in alphabetical order to ensure lex order

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 storage of all words' characters

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

Edge Cases

Empty word list

Returns empty string as no words exist

DSA Javascript

if (node !== this.root && !node.isWord) return;

Words with single character only

Returns the lex smallest single character word

DSA Javascript

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

Words where some prefixes are missing

Skips words whose prefixes are not marked as words in trie

DSA Javascript

if (node !== this.root && !node.isWord) 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.

Common Mistakes

Mistake: Not checking if each prefix is a word before continuing DFS
Fix: Add condition to stop DFS if current node is not end of a word

Mistake: Not sorting children during DFS causing incorrect lex order
Fix: Sort children keys before DFS to ensure lexicographical order

Summary

Build a trie 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 not valid words.