Longest Word in Dictionary Using Trie in DSA Typescript

Mental Model

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

Analogy: Imagine a tree of building blocks where each block is a letter. To build the tallest tower (longest word), every smaller tower below it must also be complete and stable (valid word).

root
 ↓
 a -> p -> p -> l -> e
 ↑    ↑    ↑    ↑    ↑
 w    w    w    w    w

w = word ends here (valid word)

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, mark end of word at 'a'

root -> a[w]

w = word ends here

Why: We start building the trie with the smallest word

Step 2: Insert 'ap' into trie, mark end of word at 'p'

root -> a[w] -> p[w]

w = word ends here

Why: Add next word and mark its end to track valid prefixes

Step 3: Insert 'app' into trie, mark end of word at second 'p'

root -> a[w] -> p[w] -> p[w]

w = word ends here

Why: Continue building trie with longer word and mark valid prefix

Step 4: Insert 'appl' into trie, mark end of word at 'l'

root -> a[w] -> p[w] -> p[w] -> l[w]

w = word ends here

Why: Add next prefix word to trie

Step 5: Insert 'apple' into trie, mark end of word at 'e'

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

w = word ends here

Why: Add full word to trie

Step 6: Insert 'apply' into trie, mark end of word at 'y'

root -> a[w] -> p[w] -> p[w] -> l[w] -> e[w]
                                   ↓
                                   y[w]

w = word ends here

Why: Add another full word with same prefix

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

Check 'a' (valid), 'ap' (valid), 'app' (valid), 'appl' (valid), 'apple' (valid), 'apply' (valid)

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

Step 8: Choose longest word with all prefixes valid: 'apple' or 'apply'

Longest word found: 'apple' (lexicographically smaller)

Why: Return longest word with all prefixes valid; if tie, choose lex smaller

Result:

root -> a[w] -> p[w] -> p[w] -> l[w] -> e[w]
                                   ↓
                                   y[w]

Longest word: apple

Annotated Code

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isWord: boolean = false;
}

class Trie {
  root: TrieNode = new TrieNode();

  insert(word: string): void {
    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(): string {
    let result = "";

    const dfs = (node: TrieNode, path: string): void => {
      if (node !== this.root && !node.isWord) return; // skip if prefix not a word

      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;
  }
}

// Driver code
const words = ["a", "app", "apple", "apply", "ap", "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 node if character path does not exist

node = node.children.get(char)!;

Advance node pointer to child node for next character

node.isWord = true;

Mark current node as end of a valid word

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

Stop DFS if current prefix is not a valid word

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 tie

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) where N is number of words and L is max word length because we insert each character once and DFS visits nodes once

Space: O(N * L) for trie storage as each character creates a node in worst case

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

Edge Cases

Empty list of words

Returns empty string as no words exist

DSA Typescript

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

Words with no valid prefix chain (e.g., ['b', 'ba', 'bac'] but 'b' missing)

Skips words where prefix is not a word, returns empty or shorter valid word

DSA Typescript

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

Multiple longest words with same length

Returns lexicographically smallest word due to sorted DFS traversal

DSA Typescript

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

When to Use This Pattern

When asked to find the longest word with all prefixes present in a dictionary, use a trie to efficiently check prefixes and traverse lex order.

Common Mistakes

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

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

Summary

Builds a trie from words and finds the longest word where every prefix is also a word.

Use when you need to find words with valid prefix chains efficiently.

The key is to stop exploring paths where prefixes are not words and traverse children in lex order.